Why did my program gets TLE?


  • 0
    N

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

  • 1
    S

    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.


  • 0
    N

    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!


Log in to reply
 

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