Bookings Nobody Swallowed

Medium

A meeting room keeps a list of bookings slots. Each booking [start, end) takes the time from start inclusive to end exclusive. A booking [a, b) is redundant if some other booking [c, d) in the list fully covers it: c ≤ a and b ≤ d. All redundant bookings are struck out. Return how many bookings remain.

Example 1

slots=[[2, 6], [3, 5], [7, 9], [4, 8]] → 3

The booking [3, 5) lies entirely inside [2, 6) and is struck out. None of the other three fits inside another one, so the answer is 3.

Example 2

slots=[[0, 10], [0, 4], [6, 10]] → 1

Both short bookings fit inside [0, 10), even though they share an endpoint with it. One booking remains.

Example 3

slots=[[1, 3], [3, 5]] → 2

Constraints

1 ≤ len(slots) ≤ 1000
slots[i] = [start, end], 0 ≤ start < end ≤ 10⁵
All bookings are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Distinct Orderings With Repeats Medium Anagram Buckets Medium

Input

slots=[[2, 6], [3, 5], [7, 9], [4, 8]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.