Back to DSA sheet
Insert Interval
MediumArraysGiven a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary so the result stays sorted and non-overlapping.
Input format (stdin): the first line has n. The next n lines have an interval 'start end'. The final line has the new interval 'start end'. Output the resulting intervals, one per line.
Examples
Input: 2
1 3
6 9
2 5
Output: 1 5
6 9
[2,5] merges with [1,3] into [1,5].
Input: 5
1 2
3 5
6 7
8 10
12 16
4 8
Output: 1 2
3 10
12 16
[4,8] overlaps [3,5],[6,7],[8,10] into [3,10].
Constraints
- 0 <= n <= 10^4
- intervals are sorted and non-overlapping
Sheets
Blind 75Grind 75NeetCode 150NeetCode 250
insert-interval.cpp2 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.