Citation of the authors: "Given a set of intervals (pairs of real numbers), we look at the problem of finding a minimal partition of this set such that no element of the partition contains two overlapping intervals. We exhibit a O (n log n) algorithm which is optimal. The problem has applications in LSI layout design and job scheduling".
And I add that this algorithm solves also some problems in register allocation inside compilers.
Dowload the sources under GPL licence .
int MAXIMAL_STABLE_SET_IG (const std::list< INTERVAL > & intervals, int * colour)
Below a example showing how to use this function.
#include "interval.h" #ifdef HAVE_CONFIG_H #include <config.h> #endif #include <iostream> #include <cstdlib> using namespace std; int main(int argc, char *argv[]) { std::list<INTERVAL> intervals; std::list<INTERVAL>::iterator it; int alpha, i, colour[200]; // example of the paper: U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810 intervals.push_back(INTERVAL(1,4)); intervals.push_back(INTERVAL(2,8)); intervals.push_back(INTERVAL(3,6)); intervals.push_back(INTERVAL(5,10)); intervals.push_back(INTERVAL(7,13)); intervals.push_back(INTERVAL(9,11)); intervals.push_back(INTERVAL(12,14)); alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]); cout<<"The First example is the one explained in the paper : U.I. Gupta, D.T. Lee, J.-T Leung. An optimal solution for the channel-assignment problem; IEEE Transactions on Computers C-28(1979), 807-810.\n"; cout<<"The minimal number of colours is "<<alpha<<endl; it=intervals.begin(); for(i=0;i<intervals.size();i++){ cout<<"Interval number "<<i<<" : "<<*it<<endl; cout<<"Coloured with colour number "<<colour[i]<<endl; it++; } cout<<"-----------------------------------------\n"; cout<<"Now another example. We add new intervals\n"; cout<<"-----------------------------------------\n"; // another tricky example intervals.push_back(INTERVAL(1,9)); intervals.push_back(INTERVAL(6,8)); intervals.push_back(INTERVAL(8,10)); intervals.push_back(INTERVAL(10,11)); intervals.push_back(INTERVAL(5,10)); intervals.push_back(INTERVAL(9,11)); intervals.push_back(INTERVAL(14,15)); alpha=MAXIMAL_STABLE_SET_IG(intervals, &colour[0]); it=intervals.begin(); cout<<"Now, the minimal number of colours is "<<alpha<<endl; for(i=0;i<intervals.size();i++){ cout<<"Interval number "<<i<<" : "<<*it<<endl; cout<<"Coloured with colour number "<<colour[i]<<endl; it++; } return EXIT_SUCCESS; }