my strange way ------ solve it in a list


  • 0
    J
    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            list<Interval> temp(intervals.begin(), intervals.end());
            list<Interval>::iterator it = temp.begin();
            while (it != temp.end())
            {
                if (newInterval.start >= it->start && newInterval.end <= it->end)
                    return vector<Interval>(temp.begin(), temp.end());
                if (newInterval.end < it->start && (it == temp.begin() || newInterval.start > (prev(it))->end))
                {
                    temp.insert(it, newInterval);
                    return vector<Interval>(temp.begin(), temp.end());
                }
                if (newInterval.start < it->start && newInterval.end >= it->start)
                {
                    newInterval.end = max(newInterval.end, it->end);
                    it = temp.erase(it);
                }
                else if (newInterval.end > it->end && newInterval.start <= it->end)
                {
                    newInterval.start = min(newInterval.start, it->start);
                    it = temp.erase(it);
                }
                else
                    ++ it;
            }
            temp.insert(it, newInterval);
            return vector<Interval>(temp.begin(), temp.end());
        }
    };
    

    move it to a list, and all the insert and erase shall be acted with O(1),then move it back to the vector.


Log in to reply
 

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