17. Consider the following variation on the Interval Scheduling Problem. Youu ha

Question

17. Consider the following variation on the Interval Scheduling Problem. Youu have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from what we saw in the Interval Scheduling Problem.) Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times. Example. Consider the following four jobs, specified by (start-time, end time) pairs. 6 P.M, 6 AM), (9 PM, 4 AM), (3 A.M, 2 P.M.), (1 PM, 7 PM) The optimal solution would be to pick the two jobs (9 P.M., 4 AM.) and (1 P.M, 7 P.M.), which can be scheduled without overlapping.

Explanation / Answer

Let L1, L2, L3…... Ln denotes the n intervals. An Lj-restricted solution is one that contains the interval Lj.

           The algorithm is

                   1. for fixed j,to compute an Lj-restricted solution of maximum size.

                   2.Let x be a point contained in Lj.

                  3.First delete Lj and all intervals that overlap it.

                  4.The remaining intervals do not contain the point x,so we can “cut” the

                      time-line at x and produce an instance of the interval Scheduling

                        problem from class.

              The running time of this algorithm is O(n).

Assume that the intervals are ordered by ending time.

      The algorithm is

               1. To compute an Lj restricted solution of maximum size for each j=1,….,n.

               2. Pick the largest of these solutions and claim that it is an optimal solution.

               3. Consider the optimal solution to the full problem, consisting of a

                   set of intervals S.

               4.Since n>0,there is some interval Lj belongs to S

                      but then S is an optimal Lj-restricted solution, and

                      so our algorithm will produce a solution at least as large as S.

        The running time of the algorithm is O(n2).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.