Show problems as
Classic problem #435MediumArrayDynamic ProgrammingGreedySorting

Non-overlapping Intervals

Real-world version: Drop the Clashing Kiln Runs
Tracked in this browser only
Read Non-overlapping Intervals on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMerge Intervals · Arrays, animated step by step

A ceramics studio books firings on one shared kiln. Every request comes in as a pair [start, finish] inside runs, both measured in minutes from the studio's reference mark; a request that sits earlier than the mark uses negative minutes, and a firing always finishes after it starts.

Two requests clash when the stretches of kiln time they occupy share at least one minute. A firing that finishes on the exact minute another begins does not clash with it, since the kiln is free again at that mark.

Cancel as few requests as possible so that no two survivors clash. Return how many requests you had to cancel.

Examples

Example 1

Input
runs = [[1, 4], [2, 6], [5, 9]]
Output
1

Cancelling the request that runs from 2 to 6 leaves the other two, which share no minute. Keeping all three is impossible because the middle firing clashes with both of the others.

Example 2

Input
runs = [[-3, 0], [0, 5], [5, 8]]
Output
0

Each firing finishes exactly when the next one begins, so the kiln is never double booked and nothing has to go.

Example 3

Input
runs = [[0, 10], [9, 12], [11, 20]]
Output
1

Dropping the short middle request keeps the two long firings, which never overlap. Cancelling one of the long firings instead would leave the remaining pair still clashing.

Constraints

  • 1 <= runs.length <= 10^5
  • runs[i].length == 2
  • -5 * 10^4 <= start < finish <= 5 * 10^4
  • Requests that only touch at a single minute mark do not clash

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_runs_to_cancel(runs: list[list[int]]) -> int:
Java
public int minRunsToCancel(int[][] runs)

More on the same topics