Newly Painted Length Per Day
Google● HardINTERNONSITE INTERVIEWProblem statement
A painter works for several days. On day i, the painter covers the half-open interval [paint[i][0], paint[i][1]) on a number line.
Return a long[] where index i contains the length painted for the first time on day i. Any portion covered on an earlier day must not be counted again.
Touching intervals may be coalesced because a shared endpoint has zero length under the half-open convention.
Interview extensions
- Describe an online solution that stores merged, disjoint intervals in an ordered structure and updates a running union length after each insertion.
- Explain how the overlap and adjacency rules change for closed integer intervals.
- Cover insertions that are fully contained, partially overlap one interval, or absorb several existing intervals.
Function
newlyPaintedLengths(paint: int[][]) → long[]Examples
Example 1
paint = [[1,4],[4,7],[2,5]]return = [3,3,0]The first two days add [1,4) and [4,7), each with length 3. The third interval [2,5) is already covered.
Example 2
paint = [[1,5],[2,7],[10,12],[6,11]]return = [4,2,2,3]The daily new pieces have lengths 4, 2, 2, and 3. On the last day, only [7,10) was previously unpainted.
Example 3
paint = [[0,10],[2,3],[10,12]]return = [10,0,2]The second interval is fully contained in the first. The third touches the existing union and contributes the new segment [10,12).
Example 4
paint = [[-3,0],[-1,2]]return = [3,2]The first day paints length 3. On the second day, only [0,2) is new, so the added length is 2.
Constraints
1 <= paint.length <= 200000- Each
paint[i]contains exactly two integers[left, right]. -10^9 <= left < right <= 10^9- All lengths and accumulated totals are computed with signed 64-bit arithmetic.