Spots Under the Stalls

Easy

Spots along a street are numbered 1, 2, 3, … Market stalls have been set up there: stall stalls[i] = [start, end] takes up every spot from start to end inclusive. Stalls may overlap. Return how many distinct spots are taken by at least one stall.

Example 1

stalls=[[2, 4], [8, 9], [3, 6]] → 7

Spots 2–6 are taken (two stalls overlap there) plus 8–9: 5 + 2 = 7 in total.

Example 2

stalls=[[5, 5], [5, 5]] → 1

Both stalls stand on spot 5, and it is counted only once.

Example 3

stalls=[[1, 10], [4, 7]] → 10

Constraints

1 ≤ len(stalls) ≤ 100
stalls[i] = [start, end]
1 ≤ start ≤ end ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Prefix Sum

Similar problems

Duty Days With No Gaps Easy Longest Run with a Given Sum Medium A Stretch Divisible by k Medium As Many Heads as Tails Medium Four Equal Pieces Hard

Input

stalls=[[2, 4], [8, 9], [3, 6]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.