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

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"));

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!