Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points


    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points


    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes

Consider the following variation on the Interval Scheduling Problem. You 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 A.M.), (9 P.M., 4 A.M.), (3 A.M., 2 P.M.), (1 P.M., 7 P.M.)

The optimal solution would be to pick the two jobs (9 P.M., 4 A.M.), (1 P.M., 7 P.M.), which can be scheduled without overlapping.

in Algorithms 7 points 8 views

Please log in or register to answer this question.