Interval Scheduling: Greedy AlgorithmGreedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it's compatible with the ones already taken.
Sort jobs by finish times so that f1 f2 ... fn.set of jobs selected
A for j = 1 to n { if (job j compatible with A) A A {j} } return A
Implementation. O(n log n). Remember job j* that was added last to A. Job j is compatible with A if sj fj*.