Fresh Paint Per Day

Hard

A long fence can be thought of as a number line. A painter has a plan for n days: on day i the stretch from jobs[i][0] to jobs[i][1] must be painted. Painting any spot twice leaves blotches, so the painter only covers the part of the stretch that was not painted on earlier days. Return an array of length n whose i-th element is the length of fence painted for the first time on day i.

Example 1

jobs=[[2, 6], [0, 3], [5, 9]] → [4, 2, 3]

Day 0 paints 2 to 6, length 4. On day 1 only the part from 0 to 2 of the stretch 0 to 3 is new, length 2. On day 2 the part 5 to 6 is already done, and 6 to 9 is new, length 3.

Example 2

jobs=[[10, 20], [12, 15], [0, 30]] → [10, 0, 20]

Day 1's stretch lies entirely inside paint that is already there, so it adds 0. On day 2 the new parts are 0 to 10 and 20 to 30.

Constraints

1 ≤ n = len(jobs) ≤ 10⁵
jobs[i] = [start, end], 0 ≤ start < end ≤ 5 · 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Segment Tree Array Ordered Set

Similar problems

City Block Outline Hard Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard A Dark Gap Between Street Lamps Hard

Input

jobs=[[2, 6], [0, 3], [5, 9]]

Expected

[4, 2, 3]

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