Dynamic Programming Proof:

You are scheduling a telescope to view astronomical events. Suppose the telescope can move between -85 degrees; and +85 degrees and the telescope can move 1 degree in either direction per minute. You are given a list of n celestial events. Each event has a time (in minutes since the sunset) and a location in degrees in the sky. If the telescope is pointing at that location at that minute, it can take a picture of the event. Otherwise it misses the event. Assume that taking a picture takes 1 minute and the telescope does not move during that time. Given the n events, the location and time of each event, and assuming the telescope begins the evening at position 0, give an efficient algorithm that finds a schedule that photographs the maximum number of events such that the last event in the list is photographed. Prove your algorithm is correct. State and justify the running time.