Painted Fence Length
EasyIntervals
Problem
Several volunteers painted a long fence. Volunteer i painted the half-open stretch segments[i] = [from, to), measured in metres from the gate. Stretches may overlap.
Return the total length of fence that has been painted at least once.
Example 1
- Input:
- segments = [[1, 4], [2, 6], [8, 10]]
- Output:
- 7
[1, 4) and [2, 6) together cover [1, 6) (5 m); [8, 10) adds 2 m.
Example 2
- Input:
- segments = [[0, 1], [1, 2]]
- Output:
- 2
Constraints
- 0 ≤ segments.length ≤ 10^5
- -10^9 ≤ from < to ≤ 10^9
Hint
Show the first hint
Adding up the lengths counts overlapping metres twice. What order makes overlaps easy to handle?
Walkthrough
How to approach it
01Clarify before coding
- Are the stretches half-open? Yes, so [0, 1) and [1, 2) add up to 2 m with no double count.
- Can the list be empty? Yes → 0.
- Can coordinates be negative? Yes, the gate is not necessarily the left end.
02Brute force
Mark every metre in a set and count the set.
Cost: O(total length) time and memory: up to 2·10^9 metres.
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.
This problem is part of Pro.