Sep 5, 2011

Interval Scheduling Problem or a.k.a Earliest Deadline First Scheduling

Here is another example of the greedy algorithm, "Interval Scheduling Problem". You can find detailed explanation on Wikipedia

If I explain how this algorithm can work in an instinctive way, I can say like this:
  • The earlier a job ends, the more jobs you can choose.
This is not a proof. If you want to know how to proof, please see  "Earliest deadline first scheduling" on Wikipedia. Earliest deadline first scheduling is is a dynamic scheduling algorithm used in real-time operating systems.

-----

Problem:
You have 'N' jobs. Each job starts at time 'si' and ends at time 'ti'. You have to choose join or not for each job. If you join, you must jon from the beginning to the end of the job. You cannot join more than two jobs at one time. An overlapping of start time and end time is not permitted. You want to join as much as possible. Hou many jobs can you join?

Constraint:
1 <= N <= 100000
1 <= si < ti <= 10^9

Sample input:
N = 5
s = {1, 2, 4, 6, 8}
t = {3, 5, 7, 9, 10}

Sample output:
3

My Solution:

No comments:

Post a Comment