First collect all intervals that end before the new interval begins, then merge every interval that overlaps with the new one, and finally append the rest.

Insert Interval

hard

Acceptance: 36%

IntervalsArrays

You have a sorted list of non-overlapping intervals and a new interval to add. Insert the new interval into the list, merging with any existing intervals that it overlaps, and return the updated sorted list.

Examples

Example 1:

Input:intervals = [[2,4],[7,10]], newInterval = [3,8]

Output:[[2,10]]

Example 2:

Input:intervals = [[1,2],[4,6],[8,10],[13,17]], newInterval = [5,9]

Output:[[1,2],[4,10],[13,17]]

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Insert Interval

Examples

Hints

Related Problems