Leetcode 57 - Insert Interval

Table of contents

Problem

Given an array of non-overlapping intervals intervals sorted in ascending order by start and a new interval newInterval, insert newInterval into intervals such that intervals remains sorted and non-overlapping (merging overlapping intervals if necessary).

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti, endi <= 10^5
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start, end <= 10^5

Approaches

To solve this problem, we iterate through intervals, comparing each interval to newInterval and merging them if necessary.

Linear Scan Approach

1. Add all intervals ending before newInterval starts: These intervals are not affected by the insertion.
2. Merge overlapping intervals with newInterval: If an interval overlaps with newInterval, update the newInterval to be the merged interval.
3. Add the merged newInterval: Once we reach an interval that starts after newInterval ends, add the newInterval.
4. Add remaining intervals: Add all the intervals that start after newInterval.

Solution: Linear Scan

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i = 0
        n = len(intervals)

        # Add all intervals ending before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Merge overlapping intervals with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
            i += 1
        result.append(newInterval)

        # Add remaining intervals
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

Time and Memory Complexity

The time complexity is O(N), where N is the number of intervals, as we are iterating through the intervals once. The space complexity is O(N) for the output list.

Explanation

The algorithm starts by adding intervals that don’t overlap with newInterval. Then, it merges overlapping intervals and adds the merged newInterval. Finally, it adds the remaining intervals.

Visual Representation of the Linear Scan Approach

Consider the input intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] and newInterval = [4,8].

1. Initial Intervals and New Interval:

   • Existing intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]].
   • New Interval to insert: [4,8].

2. Adding Non-Overlapping Intervals:

   • The interval [1,2] is added to the result as it ends before [4,8] starts.
   • Result: [[1,2]].

3. Merging Overlapping Intervals:

   • Interval [3,5] starts before [4,8] ends and ends after [4,8] starts, so it overlaps. Merge it with [4,8] to form [3,8].
   • Interval [6,7] falls entirely within [3,8], so the merged interval remains [3,8].
   • Interval [8,10] overlaps with [3,8]. Merge them to form [3,10].
   • After merging, the result is [[1,2], [3,10]].

4. Adding Remaining Intervals:

   • Interval [12,16] does not overlap with [3,10], so it is added to the result.
   • Final result: [[1,2], [3,10], [12,16]].

Intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]
New Interval: [4,8]

Step 1: Add non-overlapping interval [1,2]
Step 2: Merge overlapping intervals [3,5], [6,7], [8,10] with [4,8] to form [3,10]
Step 3: Add remaining interval [12,16]

Result: [[1,2], [3,10], [12,16]]