Shift Coverage Counts

EasyIntervals

Problem

A help desk is open for n hours, numbered 0 to n - 1. Each entry of shifts is [first, last]: one agent works every hour from first to last, both inclusive.

Return an array of length n whose entry h is the number of agents working during hour h.

Example 1

Input:
n = 5, shifts = [[1, 3], [0, 1], [2, 4]]
Output:
[1, 2, 2, 2, 1]

Hour 1 is covered by [1, 3] and [0, 1]; hour 2 by [1, 3] and [2, 4]; and so on.

Example 2

Input:
n = 3, shifts = []
Output:
[0, 0, 0]

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ shifts.length ≤ 10^5
  • 0 ≤ first ≤ last < n

Hint

Show the first hint

Adding 1 to every hour of every shift can cost n · shifts operations. Can you record a shift in O(1)?

Walkthrough

How to approach it

01Clarify before coding

  • Is last inclusive? Yes, so the -1 goes at last + 1.
  • Can shifts repeat? Yes, each counts separately.
  • Can there be no shifts? Yes → all zeros.

02Brute force

For each shift, loop over its hours and add 1.

Cost: O(n · m) time in the worst case: 10^10 for 10^5 full-length shifts.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.