All problems

Relay Handover Shifts

Medium · intervals

A hospital ward must have a nurse on duty at every minute from minute 0 up to, but not including, minute total. Nurses offer shifts: shifts[i] = [start, end] is a shift that begins at minute start and finishes at minute end, so the nurse is on duty from start up to, but not including, end.

Nurses must hand over in person. When one nurse is replaced by the next, the next nurse's shift has to begin at least overlap minutes before the previous nurse's shift ends, so the two work side by side for a while. With overlap = 0 the next shift may begin the very minute the previous one ends.

You pick some of the offered shifts and put them in the order they are worked. The first one must start at minute 0, each later one must start at least overlap minutes before the one before it ends, and the last one must end at minute total or later.

Return the smallest number of shifts you need, or -1 if the night cannot be covered this way. Each offered shift can be used at most once.

Examples

Example 1

Input: shifts = [[0, 6], [4, 10], [8, 14], [12, 18]], total = 18, overlap = 2

Output: 4

Each shift starts exactly 2 minutes before the previous one ends (4 = 6 - 2, 8 = 10 - 2, 12 = 14 - 2), so all four are needed.

Example 2

Input: shifts = [[0, 5], [5, 10]], total = 10, overlap = 1

Output: -1

The second shift starts at minute 5, but with a 1 minute handover it would have to start by minute 4. There is no way to cover the night.

Example 3

Input: shifts = [[0, 3], [2, 9], [1, 5], [4, 12], [8, 10]], total = 12, overlap = 1

Output: 3

Take [0, 3], then [2, 9] (starts by minute 2), then [4, 12] (starts by minute 8), which reaches minute 12.

Constraints