Show problems as
Classic problem #1288MediumArraySorting

Remove Covered Intervals

Real-world version: Prune the Patrol Log
Tracked in this browser only
Read Remove Covered Intervals on LeetCode(opens in a new tab)

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

A corridor camera writes one line into its log for every recording run. You are given windows, where windows[i] = [start_i, end_i] holds the minute mark at which run i began recording and the minute mark at which it stopped, with start_i < end_i.

Run a swallows run b when a began no later and stopped no earlier, that is a[0] <= b[0] and b[1] <= a[1].

Prune the log by deleting every run that is swallowed by some other run still listed, then return how many runs remain. No two lines of the log carry the same pair of minute marks, so no two runs swallow each other and the pruned count is well defined. The runs are in no particular order.

Examples

Example 1

Input
windows = [[2, 9], [4, 7], [3, 11], [12, 15]]
Output
3

Run [4, 7] is swallowed by [2, 9], since 2 <= 4 and 7 <= 9, so it is deleted. None of [2, 9], [3, 11] and [12, 15] is swallowed by another run, leaving 3 lines.

Example 2

Input
windows = [[0, 2], [0, 6], [0, 9]]
Output
1

Both [0, 2] and [0, 6] are swallowed by [0, 9], which began no later and stopped no earlier, so they are deleted and 1 line remains.

Example 3

Input
windows = [[2, 7], [3, 7]]
Output
1

Run [3, 7] begins later than [2, 7] and stops at the same mark, which satisfies 2 <= 3 and 7 <= 7, so it is deleted and 1 line remains.

Constraints

  • 1 <= windows.length <= 1000
  • windows[i].length == 2
  • 0 <= start_i < end_i <= 10^5
  • No two entries of windows are identical

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 count_surviving_windows(windows: list[list[int]]) -> int:
Java
public int countSurvivingWindows(int[][] windows)

More on the same topics