1100. Painted Road Length
A town is repainting the centre line of a long straight road. Every work order in segments is a pair [start, end] giving two positions, measured in metres from the depot, between which one crew lays paint in a single pass. Crews do not coordinate, so the stretches they paint may overlap, nest inside one another, or touch end to end. A second coat on the same spot adds nothing.
Return the total length of road, in metres, that receives paint at least once. A stretch with start == end covers no length at all, and the orders may be listed in any order.
Example 1
- Input:
- segments = [[1,4],[3,7],[10,12]]
- Output:
- 8
- Explanation:
The first two orders merge into positions 1 to 7 (6 m) and the last adds 2 m, so 8 m is painted.
Example 2
- Input:
- segments = [[5,8],[5,8],[6,7]]
- Output:
- 3
- Explanation:
All three orders lie inside positions 5 to 8, so only 3 m is painted.
Constraints
1 ≤ segments.length ≤ 105
segments[i] = [start, end], 0 ≤ start ≤ end ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)