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

- 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