Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Insert Interval

Medium
arrayintervals

You are given non-overlapping intervals sorted by start, plus one new interval. Insert the new interval and merge as needed so the result stays sorted and non-overlapping.

Input

  • Line 1: n 2
  • Next n lines: the existing intervals
  • Last line: the new interval start end

Output: the resulting intervals, one per line.

Example 1
Input:
2 2
1 3
6 9
2 5
Output:
1 5
6 9
Example 2
Input:
5 2
1 2
3 5
6 7
8 10
12 16
4 8
Output:
1 2
3 10
12 16

The new [4,8] swallows [3,5], [6,7], [8,10].

Constraints

  • 0 ≤ n ≤ 10^4
  • Intervals sorted by start, non-overlapping.
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.