There is a long and thin painting that can be represented by a number line. You are given a 0indexed 2D integer array paint
of length n
, where paint[i] = [start_{i}, end_{i}]
. This means that on the i^{th}
day you need to paint the area between start_{i}
and end_{i}
.
Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.
Return an integer array worklog
of length n
, where worklog[i]
is the amount of new area that you painted on the i^{th}
day.
Example 1:
222 <= x
00000011111122
0 1 2 3 4 5 6 7 8
Input: paint = [[1,4],[4,7],[5,8]]
Output: [3,3,1]
Explanation:
On day 0, paint everything between 1 and 4.
The amount of new area painted on day 0 is 4  1 = 3.
On day 1, paint everything between 4 and 7.
The amount of new area painted on day 1 is 7  4 = 3.
On day 2, paint everything between 7 and 8.
Everything between 5 and 7 was already painted on day 1.
The amount of new area painted on day 2 is 8  7 = 1.
Example 2:
2222 <= x
00000022111111
0 1 2 3 4 5 6 7 8
Input: paint = [[1,4],[5,8],[4,7]]
Output: [3,3,1]
Explanation:
On day 0, paint everything between 1 and 4.
The amount of new area painted on day 0 is 4  1 = 3.
On day 1, paint everything between 5 and 8.
The amount of new area painted on day 1 is 8  5 = 3.
On day 2, paint everything between 4 and 5.
Everything between 5 and 7 was already painted on day 1.
The amount of new area painted on day 2 is 5  4 = 1.
Example 3:
1111 <= x
00000000
0 1 2 3 4 5
Input: paint = [[1,5],[2,4]]
Output: [4,0]
Explanation:
On day 0, paint everything between 1 and 5.
The amount of new area painted on day 0 is 5  1 = 4.
On day 1, paint nothing because everything between 2 and 4 was already painted on day 0.
The amount of new area painted on day 1 is 0.
Constraints:
1 <= paint.length <= 105
paint[i].length == 2
0 <= start_{i} < end_{i} <= 5 * 10^{4}

