# Last year, this solution is accepted, but this year, this solution returns "Time Limit Exceeded".

• https://oj.leetcode.com/problems/insert-interval/

``````    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it = intervals.begin();
while(it != intervals.end())
{
// case 1: intervals = [10, 20] , newInterval = [1,2]
if(newInterval.end < (*it).start) {
intervals.insert(it, newInterval);
return intervals;
}
// case 2: intervals = [10, 20] , newInterval = [25,30]
else if(newInterval.start > (*it).end) {
it++;
}
// case 3: intervals = [10, 20] , newInterval = [5,25]
else if(newInterval.start <= (*it).start && newInterval.end >= (*it).end) {
it = intervals.erase(it);
}
// other case 4: intervals = [10, 20] , newInterval = [5,15]
//            5: intervals = [10, 20] , newInterval = [15,25]
//            6: intervals = [10, 20] , newInterval = [15,16]
else {
newInterval.start = min(newInterval.start, (*it).start);
newInterval.end = max(newInterval.end, (*it).end);
it = intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}``````

• This is because you are using `vector::erase(iterator)`, which is inefficient as it needs to move every elements after the iterator one position to its left.

• ``````/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
auto it=intervals.begin();
auto it_pre=it; //Track the head of obsolete items
while(it!=intervals.end()) {
if(newInterval.end<it->start) {
if(it!=it_pre) {
it=intervals.erase(it_pre, it); //Erase them together
intervals.insert(it, newInterval);
} else intervals.insert(it, newInterval);
return intervals;
}else if(newInterval.start>it->end) {
it++;
it_pre++;
} else {
newInterval.start=min(newInterval.start, it->start);
newInterval.end=max(newInterval.end, it->end);
it++; //Skip obsolete items
}
}
if(it!=it_pre) it=intervals.erase(it_pre, it);  //Erase them together
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
``````

This solution works.

• @wangkaimin, Really appreciate your update. It looks much better now.

• Thank you! I am confused about TLE problem too.

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