Show problems as
Classic problem #1893EasyArrayHash TablePrefix Sum

Check if All the Integers in a Range Are Covered

Real-world version: Patrol Coverage Audit
Tracked in this browser only
Read Check if All the Integers in a Range Are Covered on LeetCode(opens in a new tab)

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

A depot numbers its patrol posts with consecutive integers. The night rota is given as shifts, where shifts[i] = [from_i, to_i] means guard i walks every post numbered from_i through to_i. Both ends of a walk are included, so a guard with [4, 4] walks post 4 and nothing else.

An auditor picks the span of posts numbered first through last, again including both ends, and wants to know whether the rota leaves no hole: every post in that span must be walked by at least one guard. Different guards may cover different parts of the span, and walks may overlap or sit side by side.

Return true if every post from first to last is walked by at least one guard, and false otherwise.

Examples

Example 1

Input
shifts = [[2, 5], [6, 9]], first = 3, last = 8
Output
true

The audited posts are 3, 4, 5, 6, 7 and 8. The first guard walks 3, 4 and 5, and the second walks 6, 7 and 8, so none of the six posts is left without a guard.

Example 2

Input
shifts = [[2, 5], [7, 9]], first = 4, last = 8
Output
false

Post 6 lies inside the audited span, but the first guard stops at post 5 and the second starts at post 7, so post 6 is walked by nobody.

Example 3

Input
shifts = [[7, 7]], first = 8, last = 8
Output
false

The audited span is the single post 8, and the only guard on the rota walks post 7 alone.

Constraints

  • 1 <= shifts.length <= 50
  • shifts[i].length == 2
  • 1 <= shifts[i][j] <= 50
  • shifts[i][0] <= shifts[i][1]
  • 1 <= first <= last <= 50

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 posts_all_covered(shifts: list[list[int]], first: int, last: int) -> bool:
Java
public boolean postsAllCovered(int[][] shifts, int first, int last)

More on the same topics