Problem

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

OR

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Examples

Example 1:

1
2

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]%%  %%

Example 2:

1
2
3

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

Solution

Method 1 - Greedy

If the list was not sorted, we could have appended the newInterval to the end of list. And then the problem was Merge Overlapping Intervals.

But, given that the intervals are sorted, our task simplifies to finding the correct index where the newInterval can be placed. By We can iterate through given intervals list, and we encounter three scenarios:

  • Before New Interval (newInterval.end <interval.start): If the end of newInterval is before the start of the current interval, we insert newInterval into the list at this position.
  • After New Interval (newInterval.start > interval.end): If the start of newInterval is after the end of the current interval, we skip these intervals and eventually insert newInterval after the current interval.
  • Overlapping Intervals: When there is an overlap, we merge newInterval with the current interval. The merged interval will have: c.start=min(newInterval.start, interval.start) and c.end=max(newInterval.end, interval.end)

Here is the visual view of how the 3 cases will look. Whenever there is intersection, created a new interval.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int[][] insert(int[][] intervals, int[] newInterval) {
	List<int[]> ans = new LinkedList<>();
	for(int[] interval: intervals){
		if(interval[1] < newInterval[0]){
			ans.add(interval);
		}else if(interval[0] > newInterval[1]){
			ans.add(newInterval);
			newInterval = interval;
		}else if(interval[1] >= newInterval[0] || interval[0] <= newInterval[1]){
			int start = Math.min(interval[0], newInterval[0]);
			int end = Math.max(interval[1], newInterval[1]);
			newInterval = new int[]{start, end};
		}
	}

	ans.add(newInterval);
	return ans.toArray(int[][]::new);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

 class Solution {
     public int[][] insert(int[][] intervals, int[] newInterval) {
         List<int[]> ans = new ArrayList<>();
         int i = 0, n = intervals.length;
         
         // Add all intervals that end before newInterval starts
         while (i < n && intervals[i][1] < newInterval[0]) {
             ans.add(intervals[i++]);
         }
         
         // Merge intervals that overlap with newInterval
         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++;
         }
         ans.add(newInterval);
         
         // Add remaining intervals
         while (i < n) {
             ans.add(intervals[i++]);
         }
         
         return ans.toArray(new int[ans.size()][]);
     }
 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

 	List<Interval> ans = new ArrayList<Interval> ();

 	for (Interval interval: intervals) {
 		if (interval.end<newInterval.start) {
 			ans.add(interval);
 		} else if (interval.start > newInterval.end) {
 			ans.add(newInterval);
 			newInterval = interval;
 		} else if (interval.end >= newInterval.start || interval.start<= newInterval.end) {
 			newInterval = new Interval(Math.min(interval.start, newInterval.start), Math.max(newInterval.end, interval.end));
 		}
 	}

 	ans.add(newInterval);

 	return ans;
 }
1
2


##### Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        use std::cmp::{min, max};

        let mut ans = vec![];
        let mut new_interval = new_interval;

        for interval in intervals {
            if interval[1] < new_interval[0] {
                ans.push(interval);
            }else if interval[0] > new_interval[1] {
                ans.push(new_interval);
                new_interval = interval;
            }else {
                let start = min(interval[0], new_interval[0]);
                let end = max(interval[1], new_interval[1]);
                new_interval = vec![start, end];
            }

        }
        ans.push(new_interval);
        ans
    }
}