Insert Interval medium

Problem Statement

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

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].

Steps

1. Initialization: Create a list to store the resulting merged intervals.
2. Add Intervals Before Overlap: Iterate through the input intervals and add all intervals that are completely before the newInterval (i.e., their end time is less than the start time of newInterval) to the result list.
3. Merge Overlapping Intervals: Find the intervals that overlap with newInterval. Merge them by updating the start and end times of newInterval.
4. Add Remaining Intervals: Add the remaining intervals from intervals (those after the overlap) to the result list.
5. Handle Edge Cases: Consider cases where newInterval is completely before or after all existing intervals.

Explanation

The algorithm cleverly handles the merging process. It first adds intervals that are clearly non-overlapping with the new interval. Then, it focuses on the overlapping region, merging intervals until it finds a gap. Finally, it adds the rest of the original intervals. This ensures that all overlapping intervals are correctly merged into a single interval.

Code (Java)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;

        // Add intervals before the overlap
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Merge overlapping intervals
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Add remaining intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }

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

Complexity

• Time Complexity: O(N), where N is the number of intervals. We iterate through the intervals at most twice.
• Space Complexity: O(N) in the worst case, to store the resulting merged intervals. In the best case (no overlaps), it's O(1) additional space.

This solution provides an efficient and clear way to solve the "Insert Interval" problem in Java. The use of a List allows for dynamic addition of intervals, simplifying the merging process. Remember to handle edge cases carefully for complete correctness.