Inserting Intervals in a Sorted Array

Problem Statement

In this tutorial, we will tackle a common problem in programming: inserting a new interval into a sorted array of non-overlapping intervals. Each interval is represented as an array of two integers, where the first integer is the start time and the second integer is the end time.

Your task is to insert a new interval into the existing array while ensuring that the array remains sorted and that there are no overlapping intervals. If overlaps occur, you will need to merge them accordingly.

Finally, you will return the modified array of intervals.

Test Cases

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: The new interval [4,8] overlaps with [3,5],[6,7],[8,10], so they are merged into [3,10].

Constraints

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10⁵
• intervals is sorted by start_i in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10⁵

Intuition

The intervals array is already sorted and contains no overlapping intervals. However, inserting a new interval may create overlaps. To handle this, we will follow a systematic approach:

1. First, add all intervals that do not overlap with the new interval.
2. Next, when we reach an interval that overlaps, we will merge it with the new interval.
3. Finally, add the remaining non-overlapping intervals to the result.

Approach

Here’s a step-by-step breakdown of our approach:

• Compare the end value of the current interval with the start value of the new interval. Add all non-overlapping intervals to the result.
• For overlapping intervals, merge them by taking the minimum start time and the maximum end time.
• Add any remaining intervals to the final result array.

Complexity Analysis

• Time Complexity: O(n), where n is the number of intervals in the input array.
• Space Complexity: O(1) if we do not consider the space used for the result array.

Code Implementation

Below is a Java implementation of the approach we discussed:

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            int[][] result = new int[1][2];
            result[0][0] = newInterval[0];
            result[0][1] = newInterval[1];
            return result;
        }
        if (newInterval == null || newInterval.length == 0) {
            return intervals;
        }
        int length = intervals.length;
        List resultList = new ArrayList<>();
        int index = 0;
        while (index < length && intervals[index][1] < newInterval[0]) {
            resultList.add(intervals[index]);
            index++;
        }
        while (index < length && intervals[index][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
            index++;
        }
        resultList.add(newInterval);
        while (index < length) {
            resultList.add(intervals[index]);
            index++;
        }
        return resultList.toArray(new int[0][]);
    }
}  
                

Conclusion

In this tutorial, we learned how to insert a new interval into a sorted array of non-overlapping intervals while merging any overlaps. We discussed the problem statement, provided test cases, and walked through the solution step-by-step. With the provided code implementation, you should now be able to tackle similar problems with confidence.

Happy coding!