Consider a variant of the telescope scheduling problem, where we are given a list, L, of n observational requests for a large telescope, but now these requests are specified differently. Instead of having a start time, finish time, and benefit, each request i is now specified by a deadline, d_i, by when the observation must be completed, an exposure time, t_i, which is the length of uninterrupted telescope time this observation needs once it begins, and a benefit, bi, which, as before, is a positive integer indicating the benefit to science for performing this observation. Assume that time is broken up into discrete units, such as seconds, so that all d_i’s are integers, and observation times have an upper limit, so that all ti’s are integers in the range from 1 to n. Describe an algorithm for solving this version of the telescope scheduling problem, to maximize the total benefit of the included observations so that all the included observations are completed by their deadlines. Characterize the running time of your algorithm in terms of n.