[LeetCode] 57. Insert Interval

Problem : https://leetcode.com/problems/insert-interval/

Consider the new interval as a single item list. Since the original intervals are sorted, use merging sort alike process to merge the 2 lists.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        Deque<int[]> result = new LinkedList<>();

        boolean added = false;
        int i = 0;

        while (i <= intervals.length) {
            int[] next;

            if (i < intervals.length && (added || intervals[i][0] <= newInterval[0])) {
                next = intervals[i];
                i += 1;
            } else if (!added) {
                next = newInterval;
                added = true;
            } else {
                break;
            }

            if (result.peekLast() == null || result.peekLast()[1] < next[0]) {
                result.offerLast(next);
            } else {
                result.peekLast()[0] = Math.min(result.peekLast()[0], next[0]);
                result.peekLast()[1] = Math.max(result.peekLast()[1], next[1]);
            }
        }

        return result.toArray(new int[0][0]);
    }
}

Binary search based solution:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        newStart, newEnd = newInterval
        
        # find the lower bound insertion position
        left, right = 0, len(intervals)
        while left < right:
            mid = left + (right - left) // 2
            
            start, end = intervals[mid]
            
            if start <= newStart <= newEnd <= end:
                return intervals
            
            if start < newStart:
                left = mid + 1
            elif start > newStart:
                right = mid
            else: # start == newStart
                right = mid
        
        if left == len(intervals):
            intervals.append(newInterval)
        
        intervals.insert(left, newInterval)
        
        # merge intervals
        i = j = left - 1 if left - 1 >= 0 else 0
        
        while j < len(intervals):
            if intervals[i][0] <= intervals[j][0] <= intervals[i][1]:
                intervals[i][0] = min(intervals[i][0], intervals[j][0])
                intervals[i][1] = max(intervals[i][1], intervals[j][1])
            else:
                i += 1
                intervals[i][0] = intervals[j][0]
                intervals[i][1] = intervals[j][1]
                
            j += 1
       
        return intervals[:i+1]

Updated on 01/15/2023. Updated the linear scan approach with a concise implementation.