Given a set of overlapping intervals of the form (start, end), each of which is associated with a property (say S), print a sequence of disjoint intervals with all properties valid in that interval

Problem
/*
    Algo:
            1. make a list from all mins and maxes from the given intervals
            2. sort and remove duplicates from the list
            3. construct intervals from every two consecutive numbers from the list and check whether this interval
                is included by the given set of intervals
*/

#include <string>
#include <list>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>

using namespace std;

struct Interval{

int mn, mx;
string attr;

Interval(int _mn, int _mx, string _s=""):mn(_mn), mx(_mx), attr(_s){}

bool operator < (const Interval &i) const {

return mn < i.mn || mx < i.mx;
}

bool includes(const Interval &i) const {

return i.mn >= mn && i.mx <= mx;
}

};

ostream& operator << (ostream &o, const Interval &i ){

return o <<"(" <<i.mn<<","<<i.mx<<","<<i.attr<<")";
}



typedef set<Interval> Set;


void disjoint(Set s){

Set::iterator it;

list<int> l;


for(it = s.begin(); it != s.end(); ++it ){
l.push_back(it->mn);
l.push_back(it->mx);
}

l.sort();
l.unique();

Set out;

list<int>::iterator lit = l.begin();

int start = l.front(), end;

for(++lit; lit != l.end(); ++lit){

end = *lit;

Interval i(start, end);

for(it = s.begin(); it != s.end(); ++it ){

if(it->includes(i)) {
if(i.attr != "")
i.attr += "," + it->attr;
else
i.attr = it->attr;
}
else if(it->mn > end){
break;
}
}

if(i.attr != "")
out.insert(i);

start = end;

}

copy(out.begin(), out.end(), ostream_iterator<Interval>(cout, "\n"));

}


int main(){

Set s;

s.insert(Interval(1, 3, "S0"));
s.insert(Interval(2, 3, "S1"));
s.insert(Interval(3, 6, "S2"));
s.insert(Interval(4, 7, "S3"));
s.insert(Interval(5, 6, "S4"));
s.insert(Interval(8, 9, "S5"));

disjoint(s);

return 0;

}
Advertisements

2 thoughts on “Given a set of overlapping intervals of the form (start, end), each of which is associated with a property (say S), print a sequence of disjoint intervals with all properties valid in that interval

  1. are you assuming elements in the set are ordered with left(min) value? this one does not work if it has following elements in the setSet s; s.insert(Interval(1, 3, "S0")); s.insert(Interval(1, 3, "S1"));//replaching 2 by 1 s.insert(Interval(3, 6, "S2")); s.insert(Interval(4, 7, "S3")); s.insert(Interval(5, 6, "S4")); s.insert(Interval(8, 9, "S5"));

  2. I am wondering if this problem could possibly be modified to something like this:Find all solutions where in every solution every property must have its own interval.Solution explanation:Every property must have only one interval.All intervals are non overlapping.Find all solutions.input:(0,2,S0),(2,4,S0),(5,7,S0)(0,3,S1),(5,8,S1)(3,5,S2)output:1 (0,2,S0),(5,8,S1),(3,5,S2)2 (5,7,S0),(0,3,S1),(3,5,S2)Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s