luyangkk
BAN USERC++ simple implement (nlog(n))
My version do not treat the non overlapping intervals and the merging intervals separately, just put them together and sort those intervals. Finally, merge the overlapping intervals.
class Interval {
public:
int start, end;
Interval(int start, int end) {
this->start = start;
this->end = end;
}
bool operator<(const Interval &rhs) const {
if (this->start == rhs.start) {
return this->end < rhs.end;
}
return this->start < rhs.start;
}
};
vector<Interval> foo(vector<Interval> &v) {
sort(v.begin(), v.end());
vector<Interval> r;
Interval cur = v.front();
for (vector<Interval>::iterator i = v.begin() + 1; i != v.end(); i++) {
if (i->end <= cur.end) {
continue;
}
if (i->start <= cur.end) {
cur.end = i->end;
} else {
r.push_back(cur);
cur = *i;
}
}
r.push_back(cur);
return r;
}
An implementation of the "fast and slow pointers" solution. The fast pointer moves two steps every time and the slow pointer only moves one step. If they meet at some point then there is a loop.
- luyangkk December 31, 2013