D
BAN USERSort the list of intervals and just iterate through them - Simple O(n+m) solution as others have shown
class Interval {
public:
int _start;
int _end;
int getLength() { return (_end - _start); };
Interval(int i, int j) : _start(i), _end(j) {};
bool operator<(Interval &i1);
bool operator() (Interval &i1, Interval &i2);
};
bool Interval::operator< (Interval &i1) {
return (i1._start < _start);
}
bool Interval::operator() (Interval &i1, Interval &i2) {
return (i1._start < i2._start);
}
bool classComp(Interval *i1, Interval *i2) {return (i1->_start < i2->_start);}
void findFreeCalendarTimes() {
vector<Interval *> I1, I2;
vector<Interval *>::iterator it;
I1.push_back(new Interval(1,5));
I1.push_back(new Interval(10,14));
I1.push_back(new Interval(19,20));
I1.push_back(new Interval(21,24));
I1.push_back(new Interval(27,30));
I1.push_back(new Interval(3,5));
I1.push_back(new Interval(12,15));
I1.push_back(new Interval(18,21));
I1.push_back(new Interval(23,24));
sort(I1.begin(), I1.end(), classComp);
for(it=I1.begin(); it!=I1.end(); it++) cout << " " << (*it)->_start << " " << (*it)->_end << endl;
it = I1.begin();
int prev_end = (*it)->_end;
for(it=I1.begin(); it!=I1.end(); it++) {
if(prev_end<(*it)->_start) {
cout << "Found " << prev_end+1 << " " << (*it)->_start-1 << endl;
prev_end = (*it)->_end;
}else {
if(prev_end < (*it)->_end)
prev_end = (*it)->_end;
}
}
}
O(m*n*logn)
void findAnagrams(){
vector<string> svec;
vector<string>::iterator vit;
map< string , list<string> > m;
map< string , list<string> >::iterator mit;
list<string>::iterator lit;
list<string>::iterator eit;
svec.push_back("cars");
svec.push_back("arcs");
svec.push_back("trees");
svec.push_back("steer");
svec.push_back("scar");
svec.push_back("torn");
svec.push_back("link");
svec.push_back("kiln");
//O(m*n*logn)
int pos=0;
for(vit=svec.begin(); vit!=svec.end(); vit++ ) {
string ss = sorted(*vit);
mit = m.find(ss);
if( mit != m.end() ) {
mit->second.push_back(*vit);
}else {
list<string> ls;
ls.push_back(*vit);
m[ss] = ls;
}
pos++;
}
//O(m)
pos=0;
for(mit=m.begin(); mit!=m.end(); mit++) {
lit = mit->second.begin();
eit = mit->second.end();
for(;lit!=eit;lit++) {
cout << *lit << " ";
}
cout << endl;
}
return;
}
Repseffreyclifford, Area Sales Manager at Achieve Internet
I am a self-motivated office administrator. I am responsible for providing administrative support to office personnel. I have excellent written ...
This will also change the order of the elements which may be undesirable.
- D December 19, 2014