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


  • 1
    W

    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;
    }

  • 0
    S

    Hey @wangkaimin, when you need a hand on debug code, would you mind clarify your thoughts first? Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    W

    I've added comments. Is that OK?


  • 8

    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.


  • 3
    F
    /**
     * 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.


  • 0
    S

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


  • 0
    G

    Thank you! I am confused about TLE problem too.


Log in to reply
 

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