You are given a list of half-open intervals.
Each interval represents a segment on the number line in the form [start, end).
We paint the intervals one by one in the given order.
For each interval, return the size of the part that has not already been painted by any previous interval.
Return a list where the value at index i is the size of the newly painted segment contributed by the ith interval.
The size of a half-open interval [start, end) is end - start.
In this problem, each interval is provided as a string in the format "start,end".
Class
IntervalPainting
Method
amountPainted
List<Integer> amountPainted(List<String> intervals)
intervals.size() >= 1Each interval string is in the format "start,end"0 <= start < endEach interval represents a half-open interval [start, end)The answer at index i is the size of the segment not painted by previous intervals
Parameters
intervals
A list of strings where each string is in the format "start,end".
For example, "1,10" represents the half-open interval [1, 10).
Returns
Return a List<Integer> where each value represents how much of that interval was not painted before it was processed.
Constraints
1 <= intervals.size() <= 10^50 <= start < end <= 10^81 <= intervals.size()Each intervals[i] contains exactly one commaEach parsed interval satisfies 0 <= start < endIntervals are processed in the given orderPreviously painted parts must not be counted again
Examples
Example 1
amountPainted(intervals = ["1,10", "8,14"])
Returns [9, 4]
Explanation:
The first interval is [1, 10). Nothing was painted before, so the entire size 10 - 1 = 9 is newly painted.
The second interval is [8, 14). The part [8, 10) was already painted, so only [10, 14) is newly painted. Its size is 14 - 10 = 4.
Example 2
amountPainted(intervals = ["1,5", "2,4", "5,8"])
Returns [4, 0, 3]
Explanation:
[1, 5) contributes 4.
[2, 4) is fully inside an already painted segment, so it contributes 0.
[5, 8) does not overlap with previously painted parts in a half-open way, so it contributes 3.
Example 3
amountPainted(intervals = ["3,7", "1,4", "6,9"])
Returns [4, 2, 2]
Explanation:
[3, 7) contributes 4.
[1, 4) has only [1, 3) unpainted, so it contributes 2.
[6, 9) has only [7, 9) unpainted, so it contributes 2.