Insert Interval – 56. LeetCode

The Insert Interval problem involves inserting a new interval into a sorted list of non-overlapping intervals and merging any overlapping intervals. Think of it like scheduling a new meeting in a calendar: you add the meeting and merge it with existing ones if they overlap, ensuring the schedule remains clean and non-overlapping.

This problem models real-world scenarios like scheduling tasks, merging meeting times, or handling database ranges efficiently.

Brute Force Approach

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

public class InsertIntervalBruteForce {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[1] < newInterval[0]) {
                result.add(interval); // Interval ends before newInterval starts
            } else if (interval[0] > newInterval[1]) {
                result.add(newInterval); // Add newInterval before this interval
                newInterval = interval; // Update newInterval for later
            } else {
                // Overlap: merge intervals
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        result.add(newInterval); // Add the remaining interval
        return result.toArray(new int[result.size()][]);
    }
}

Explanation:

1. Iterate through the list of intervals.

2. Handle three cases:

• No overlap before: Add the interval directly to the result.
• No overlap after: Add newInterval and process the current interval as the new one.
• Overlap: Merge the intervals by updating the start and end times of newInterval.

Why it works:

This brute force approach iterates through all intervals and ensures that the new interval is merged correctly. It’s straightforward but less efficient due to redundant processing.

Optimal Approach & Data Structure

1. Algorithm:

• Use a single pass over the intervals to separate disjoint intervals (before and after) from the overlapping ones.

• Merge overlapping intervals on-the-fly and build the result incrementally.

2. Data Structure:

• Use a list to store the result dynamically.

The intervals are sorted, so:

• All intervals before the new interval will not overlap and can be added directly.

• All intervals after the merged interval can also be added directly.

• Overlapping intervals can be merged during the traversal, reducing extra passes or complex checks.

Steps of the Algorithm

1. Initialize a result list
2. Traverse through the intervals:
   • Add all intervals that end before the newIntertval starts
   • Merge overlapping intervals into the newInterval.
   • Add all intervals that start after the newInterval ends.
3. Append the merged newInterval to the result.
4. Return the result as an array

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

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

        // Add intervals that end before the newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Merge overlapping intervals
        while (i < n && 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 intervals that start after the newInterval ends
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

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

Line-by-Line Breakdown

1. Initialize the Result List:

List<int[]> result = new ArrayList<>();
int i = 0;
int n = intervals.length;

• A list is used to store the merged intervals
• Think of it as a growing schedule of meetings that start non-overlapping.

2. Add Non-Overlapping Intervals Before the New Interval

while (i < n && intervals[i][1] < newInterval[0]) {
    result.add(intervals[i]);
    i++;
}

• Iterates through intervals where the end of the current interval (invervals[i][1]) is strictly less than the start of the new interval (newInterval[0]).
• Adds these intervals directly to the result list since they do now overlap with newInterval

3. Merge Overlapping Intervals

while (i < n && 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);

• For overlapping meetings, adjust the start time of the new meeting to the earliest start and the end time to the latest end.
• Keep merging until no more overlaps exists.
• Add the merged meeting to the result.
• This step ensures that overlapping meetings and the new meeting are combined into a single block.

Step 4: Add Remaining Non-Overlapping Meetings

while (i < n) {
    result.add(intervals[i]);
    i++;
}

• Iterates through intervals that overlap with newInterval:
  • Overlaps exists if the start of the current interval (intervals[i][0]) is less than or equal to the end of the new interval.
• Updates newInterval:
  • Adjusts the start to the smaller of the two start times.
  • Adjusts the end to the larger of the two end times.
• Once all overlapping intervals are processed, adds the merged newInterval to the result.

Step 5: Add Non-Overlapping Intervals After the New Interval

while (i < n) {
    result.add(intervals[i]);
    i++;
}

1. Iterates through intervals that occur after the newInterval.
2. Adds these intervals directly to the result since they don’t overlap.
3. These intervals don’t require merging and can be added as-is.

Step 6: Convert List to Array

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

• Convert the result list into a 2D array to match the expected output format.

Why This Approach Works

1. Simple Logic: Divide the problem into three clear phases: before, during, and after overlaps.

2. Efficiency: Process each meeting exactly once (O(n)).

3. Correctness: Maintain the sorted order and merge intervals dynamically, ensuring no conflicts.

This code mirrors how we naturally handle scheduling, making it both intuitive and efficient.