Show problems as
Classic problem #1353MediumArrayGreedySortingHeap (Priority Queue)

Maximum Number of Events That Can Be Attended

Real-world version: Most Inspections Booked
Tracked in this browser only
Read Maximum Number of Events That Can Be Attended on LeetCode(opens in a new tab)

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

A safety office has one inspector and a list of sites waiting to be inspected. Entry windows[i] = [opens, closes] means site i may be inspected on any single whole day from day opens to day closes inclusive.

The inspector carries out at most one inspection per day and needs the whole day for it. A site is either inspected on one day inside its window or not inspected at all, and days may be left empty.

Return the largest number of sites the inspector can get through.

Examples

Example 1

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

The second site is inspected on day 1, its only day, and the first site on day 2, which is inside its window of days 1 to 2.

Example 2

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

All three windows span days 1 to 3, so the inspector takes one site on each of those days.

Example 3

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

Day 1 takes one of the two sites whose window is that single day, and day 2 takes the third site. The remaining site has no day left inside its window.

Constraints

  • 1 <= windows.length <= 10^5
  • windows[i].length == 2
  • 1 <= windows[i][0] <= windows[i][1] <= 10^5

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

More on the same topics