Last active
July 12, 2018 17:58
-
-
Save arkanath/8881497 to your computer and use it in GitHub Desktop.
Interval Partitioning Problem - Pseudocode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Problem: Given intervals with finish and end times, partition the intervals into labels with minimum amount of labels so that no two intervals in any label overlap. | |
Algorithm: | |
* Sort Intervals w.r.t. starting time, breaking tries arbitrarily. | |
* Let them be I1, I2, ... , In | |
* For j = 1:n | |
* For each (i<j && Ii,Ij overlap) | |
* Exclude the label of Ii from considering for Ij | |
* EndFor | |
* If (there exists any label not assigned from 1 to d) Assign that to Ij | |
* Else Leave Ij unlabeled | |
* EndFor | |
Analysis: | |
* None remained unlabeled if d is the maximum number of intervals that overlap together, proof by contradiction | |
* Hence d is the depth | |
* no algorithm can have better no. of labels than depth | |
* hence optimal | |
* O(n2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment