Amount of New Area Painted Each Day — Hard Algorithm Question with Solution
This is a hard question asked by Google in the interviews. In this blogpost, I will explain the solution.
There are some solutions posted in discussion section of Leetcode, but they are hard to understand. There are two approaches in the solutions.
First one is jumping line. In this solution, you need to create an array representing the painting line. Then you mark the line with the end value of the area if it is not marked before. If it is marked, then you jump to the end of the area and continue marking from there. Drawback is that you need to create a line array in advance with the size of the max value of the end value space. This is not the best solution.
Second approach is using merging areas and adding the diff of the areas until there is no merge. This type also has two approaches. First one is explained in discussion sections of Leetcode, but it is hard to understand and implement. This approach initially finds the first intersecting area. Then calculates the diff using the following algorithm:
- Calculate the all area of AREA_2.
(c+b)
2. Remove AREA_1 from AREA_2 as if all of AREA_1 is intersecting.
(c+b)-(a+c) = b-a
3. Then add back the the over removed areas.
(b-a)+a = b
