Skip to content

Instantly share code, notes, and snippets.

@arkanath

arkanath/Interval Scheduling Problem - Pseudocode

Created February 8, 2014 10:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save arkanath/8881598 to your computer and use it in GitHub Desktop.
Save arkanath/8881598 to your computer and use it in GitHub Desktop.
Download ZIP
Interval Scheduling Problem - Pseudocode
Raw
Interval Scheduling Problem - Pseudocode
Problem: Given set of intervals with starting time and end time, give the set of intervals with maximum cardinality such that no intervals overlap.
Algorithm:
* Initially let R be the set of all requests.
* While R is not empty:
* Choose a request i with earliest finish time
* add to queue A
* delete all incompatible from R.
* EndWhile
* Return A
Analysis:
* A is compatible
* A is optimal with the "Stays Ahead" argument.
* Running Time : O(n logn)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment