All problems

Pier Lamp Darkness

Medium · intervals

A long pier has a row of lamps. You are given lamps, where each item [on, off] means that lamp is switched on at minute on and switched off at minute off, so it shines from minute on up to, but not including, minute off. Lamps can overlap in time and come in no particular order.

The night watch starts at minute dusk and ends at minute dawn, so it consists of the minutes dusk, dusk + 1, ..., dawn - 1. Some lamps may be lit only partly during the night, or not at all.

Return how many minutes of the night have no lamp shining.

Examples

Example 1

Input: lamps = [[2, 5], [4, 8], [12, 14]], dusk = 0, dawn = 16

Output: 8

The lamps cover minutes 2 to 7 and 12 to 13, which is 8 minutes. The other 8 minutes of the night are dark.

Example 2

Input: lamps = [], dusk = 3, dawn = 10

Output: 7

With no lamps all 7 minutes of the night are dark.

Example 3

Input: lamps = [[1, 6], [8, 30]], dusk = 4, dawn = 10

Output: 2

Only minutes 4, 5, 8 and 9 are lit inside the night, so minutes 6 and 7 are dark.

Constraints