v9.1.1
Menu

Non-overlapping Intervals

mediumFREEIntervalsBlind 75

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 Blind 75

solution.py

Test results

Sign in to run your code against the test cases.