Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Non-overlapping Intervals

Medium
greedyintervalssorting

Given intervals [start, end), return the minimum number of intervals to remove so the rest don't overlap (touching endpoints don't overlap).

Input

  • Line 1: n 2
  • Next n lines: start end

Output: the minimum removals.

Example 1
Input:
4 2
1 2
2 3
3 4
1 3
Output:
1

Remove [1,3].

Example 2
Input:
3 2
1 2
1 2
1 2
Output:
2
Example 3
Input:
2 2
1 2
2 3
Output:
0

Constraints

  • 1 ≤ n ≤ 10^5
  • -5·10^4 ≤ start < end ≤ 5·10^4
Watch a video walkthrough

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