Leetcode 57. Insert Interval

Problem Explanation

This problem is about interval management. You are given a collection of intervals (two integer arrays representing the start and end of each interval) that are sorted based on their starting times and not overlapping. You are then given a new interval to be inserted. There are two scenarios to consider:

1. If the new interval does not overlap with any of the existing intervals, it's simply inserted at the correct position to maintain the sorted order.

2. If the new interval overlaps with one or more existing intervals, all overlapping intervals need to be merged into a single interval that spans from the earliest start time to the latest end time involved in the overlappings.

Solution Approach

The solution constantly checks three different sections, each related to the new interval:

1. The intervals that end before the new interval starts: These intervals do not overlap with the new interval thus, are simply added to the result list without any changes.

2. The intervals that overlap with the new interval: For each of these intervals, we amend the new interval to ensure it spans from the earliest start to the latest end.

3. The intervals that start after the new interval ends: These intervals also do not interact with the new interval, thus are added to the result list without any changes.

We traverse the existing intervals and based on the above conditions, we add intervals to the result list and update the newInterval if necessary.

Example

Let's consider the example of intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8].

We iterate over the intervals:

• [1,2] ends before [4,8] starts, so we add [1,2] to the result.
• [3,5] overlaps with [4,8], so we merge them into [3,8] which becomes our new interval.
• [6,7] overlaps with our new interval [3,8], so we merge them into [3,8] (No change).
• [8,10] overlaps with [3,8], so we merge them into [3,10] which becomes out new interval.
• [12,16] starts after [3,10] ends, so we add [3,10] and [12,16] to the result.

So the output is [[1,2],[3,10],[12,16]].

Java Solution

1
2java
3class Solution {
4    public int[][] insert(int[][] intervals, int[] newInterval) {
5        List<int[]> ans = new ArrayList<>();
6        int i = 0;
7
8        // Add the intervals ending before newInterval starts 
9        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
10            ans.add(intervals[i++]);
11        }
12
13        // Merge the overlapping intervals.
14        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
15            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
16            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
17            i++;
18        }
19
20        ans.add(newInterval);
21
22        // Add the intervals starting after newInterval ends.
23        while (i < intervals.length) {
24            ans.add(intervals[i++]);
25        }
26
27        return ans.toArray(new int[ans.size()][]);
28    }
29}

In this Java solution, we make use of ArrayList to store the intervals. At the end we convert the ArrayList into an array to return.

Please note: The availability of python, java, javascript, c++, c# implementations would depend on the platform where the problem is posted. If it's leetcode, it supports all these languages.

Python Solution

In python, we will follow a similar approach. However, python being a dynamically typed language has a significant advantage over Java when it comes to handling lists.

1
2python
3def insert(intervals, newInterval):
4    ans = []
5    i = 0
6
7    # Add the intervals ending before newInterval starts.
8    while i < len(intervals) and intervals[i][1] < newInterval[0]:
9        ans.append(intervals[i])
10        i += 1
11
12    # Merge the overlapping intervals.
13    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
14        newInterval[0] = min(newInterval[0], intervals[i][0])
15        newInterval[1] = max(newInterval[1], intervals[i][1])
16        i += 1
17
18    ans.append(newInterval)
19
20    # Add the intervals starting after newInterval ends.
21    while i < len(intervals):
22        ans.append(intervals[i])
23        i += 1
24
25    return ans

JavaScript Solution

JavaScript also has dynamic typing thus we don't need to worry about defining the size of arrays.

1
2javascript
3function insert(intervals, newInterval) {
4    const ans = [];
5    let i = 0;
6    
7    // Add the intervals ending before newInterval starts.
8    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
9        ans.push(intervals[i]);
10        i++;
11    }
12
13    // Merge the overlapping intervals.
14    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
15        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
16        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
17        i++;
18    }
19
20    ans.push(newInterval);
21
22    // Add the intervals starting after newInterval ends.
23    while (i < intervals.length) {
24        ans.push(intervals[i]);
25        i++;
26    }
27
28    return ans;
29}

In all the solutions, the complexity is dominated by the traversal of the intervals so the time complexity is O(n) where n is the number of intervals. The space complexity is also O(n) as we are storing the result in a separate array.