Interval Partitioning Problem - Pseudocode

Interval Partitioning Problem - Pseudocode

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)