57. Insert Interval - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        self.insertInterval(intervals, newInterval)
        print(intervals)
        return self.mergeIntervals(intervals)
    
    def insertInterval(self, intervals: List[List[int]], newInterval: List[int]):
        if not intervals:
            intervals.append(newInterval)
            return

        low, high = 0, len(intervals)-1
        while low + 1 < high:
            mid = low + (high - low) // 2
            if intervals[mid][0] < newInterval[0] or (intervals[mid][0] == newInterval[0] and intervals[mid][1] <= newInterval[1]):
                low = mid
            else:
                high = mid
        if intervals[low][0] > newInterval[0] or (intervals[low][0] == newInterval[0] and intervals[low][1] > newInterval[1]):
            intervals.insert(low, newInterval)
        elif intervals[high][0] > newInterval[0] or (intervals[high][0] == newInterval[0] and intervals[high][1] > newInterval[1]):
            intervals.insert(high, newInterval)
        else:
            intervals.append(newInterval)

    def mergeIntervals(self, intervals: List[List[int]]):
        res = []
        for a, b in intervals:
            if not res or a > res[-1][1]:
                res.append([a, b])
            else:
                res[-1][1] = max(res[-1][1], b)
        return res

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        bisect.insort(intervals, newInterval)
        res = []
        for start, end in intervals:
            if not res or res[-1][1] < start:
                res.append([start, end])
            else:
                res[-1][1] = max(res[-1][1], end)
        return res

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i].end < newInterval.start) {
                res.push_back(intervals[i]);
            }
            else if (intervals[i].start > newInterval.end) {
                res.push_back(newInterval);
                res.insert(res.end(), intervals.begin() + i, intervals.end());
                return res;
            }
            else { //intervals[i].start <=  newInterval.end && intervals[i].end >= newInterval.start
                //overlap
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            }
        }
        res.push_back(newInterval);
        return res;
    }

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        int i = 0;
        while (i < intervals.size()) {
            if (newInterval.start > intervals[i].end) { //former of newInterval
                i++;
            } else if (newInterval.end < intervals[i].start) { //latter of newInterval
                intervals.insert(intervals.begin() + i, newInterval);
                return intervals;
            } else { //intersection: newInterval.start <= intervals[i].end && newInterval.end >= intervals[i].start
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
                intervals.erase(intervals.begin() + i);
            }
        }
        intervals.push_back(newInterval); //newInterval.start > intervals.back().end
        return intervals;
    }