0239MediumArraySorting

Prune the Patrol Log

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_surviving_windows(windows: list[list[int]]) -> int:

Java

public int countSurvivingWindows(int[][] windows)

The intended approach

Time O(n log n)Space O(n) for the sorted copy of the log

Order the runs by start mark ascending and, where two runs share a start mark, by stop mark descending. Reading in that order, a run is swallowed exactly when its stop mark fails to beat the furthest stop mark already seen: every earlier run in the order began no later than it. So one sweep counting the runs that push the furthest stop mark forward gives the pruned size. The tie-break on the stop mark is what puts the wider of two runs sharing a start mark first.

Pythonentry point: count_surviving_windows

def count_surviving_windows(windows):
    order = sorted(windows, key=lambda run: (run[0], -run[1]))
    kept = 0
    furthest = -1
    for start, end in order:
        if end > furthest:
            kept += 1
            furthest = end
    return kept

The obvious version

For each run, scan every other run and ask directly whether it swallows this one; count the runs nothing swallows. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_surviving_windows(windows):
    total = len(windows)
    kept = 0
    for i in range(total):
        swallowed = False
        for j in range(total):
            if i == j:
                continue
            if windows[j][0] <= windows[i][0] and windows[i][1] <= windows[j][1]:
                swallowed = True
                break
        if not swallowed:
            kept += 1
    return kept

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in