# Why did my program gets TLE?

• My thought is to sort the intervals firstly, and then merge it.

``````bool cmp(Interval a, Interval b) {
if (a.start != b.start) return a.start < b.start;
else return a.end < b.end;
}
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
if (intervals.size() < 2) return intervals;

sort(intervals.begin(), intervals.end(), cmp);

vector<Interval>::iterator iter;
iter = intervals.begin();
for (int i = 0; i < intervals.size() - 1; ) {
if (intervals[i + 1].start <= intervals[i].end) {
intervals[i + 1].start = intervals[i].start;
if (intervals[i + 1].end < intervals[i].end) intervals[i + 1].end = intervals[i].end;
intervals.erase(iter);
} else {
i++;
iter++;
}
}
return intervals;
}
};``````

• Know that vector::erase() is a quite expensive (Up to O(n)) operation since it requires all elements after the deleted elements to be relocated. As a result, the worst case of your algorithm is O(N^2). Instead, you may want to create another empty vector, and then iteratively copy or merge from the input vector to the end of the new vector.

• Thank you so much. Your point is right!
I have submitted my new code and it was accepted.
I use a new vector to store the result and let intervals = ans to return, as your suggestion.
Thanks again!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.