v9.1.1
Menu

Non-overlapping Intervals

mediumPROGreedy & IntervalsAmazon DSA

Given intervals [start, end], return the minimum number of intervals to remove to make the rest non-overlapping.

Intervals that only touch at an endpoint (e.g. [1, 2] and [2, 3]) do not overlap.

Input: intervals is a list of [start, end] pairs (the example shows them as start:end comma-separated). Return the count as an integer.

Example

Input
1:2,2:3,3:4,1:3
Output
1
Reasoning
  • The input 1:2,2:3,3:4,1:3 is four intervals: [1,2][1,2], [2,3][2,3], [3,4][3,4] and [1,3][1,3]. Two intervals overlap only if they share more than a single point, so [1,2][1,2] and [2,3][2,3], which just touch at 22, are compatible.
  • Check every pair: [1,3][1,3] overlaps [1,2][1,2] on the stretch from 11 to 22, and overlaps [2,3][2,3] on the stretch from 22 to 33. Every other pair either touches at one endpoint or is disjoint.
  • So the answer cannot be 00: the intervals as given contain two conflicts, and both involve [1,3][1,3].
  • Removing [1,3][1,3] leaves [1,2][1,2], [2,3][2,3], [3,4][3,4], which sit end to end with no overlap. Removing any other single interval leaves at least one conflict with [1,3][1,3] in place.
  • The minimum is therefore 1. Notice that this is the same as 4−34 - 3: the total count minus the size of the largest set of intervals that can all be kept together.

Constraints

  • 1 <= len(intervals) <= 10^5
  • -5 * 10^4 <= start < end <= 5 * 10^4

Learn this in

More from Amazon DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.