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.

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. Add intervals that do not overlap with the new interval directly to the result.

3. Merge overlapping intervals by adjusting the bounds of the newInterval.

4. Finally, add any remaining intervals to the result.

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

Algorithm and Data Structure

Chosen Algorithm: Iterative merging with a single pass through the intervals.

Data Structures Used:

• Array/List: To store the final merged intervals.

1. Sorting Property of Intervals:

The input intervals are sorted by start times. This allows us to process them sequentially and easily determine if an interval overlaps with the new interval.

2. Efficient Handling of Overlaps:

Instead of repeatedly modifying the list, merge intervals dynamically by updating the bounds of the newInterval when overlaps occur.

3. Segmentation of Input:

Process intervals in three phases:

• Intervals entirely before the newInterval.

• Intervals overlapping with the newInterval.

• Intervals entirely after the newInterval.

This structured approach ensures we only traverse the input once.

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<>();

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

2. Add Meetings That End Before The New Meeting Starts:

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

• Iterate through intervals that end before the newInterval starts.
• These intervals can be safely added without any changes.
• This ensures that all non-overlapping meetings before the new meeting are handled efficiently.

3. Merge Overlapping Meetings

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++;
}

• Add all meetings that occur entirely after the new meeting.
• Simply append them to the result list.
• This step ensures the final schedule includes all remaining valid meetings after the new meeting.

Step 5: Return the Updated Calendar

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

• Convert the result list into a 2D array to math the expected output format.
• The algorithm outputs the updated schedule in the required 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.