Learning On the Way

2158. Amount of New Area Painted Each Day

There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [starti, endi]. This means that on the ith day you need to paint the area between starti and endi.

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 ith day.

Line sweep

Here it is using heap. If you use a binary search tree (SortedList), the logic is more natural

class Solution(object):
    def amountPainted(self, paint):
        """
        :type paint: List[List[int]]
        :rtype: List[int]
        """
        points = collections.defaultdict(list)
        for i, (s, e) in enumerate(paint):
            points[s].append((True, i))
            points[e].append((False, i))
        min_heap = []
        exited = [False]*len(paint)
        result = [0]*len(paint)
        prev = -1
        for pos in sorted(points.iterkeys()):
            while min_heap and exited[min_heap[0]]:
                heapq.heappop(min_heap)

            # Till this point, the segment right before this event is for the one with highest priority
            if min_heap:
                result[min_heap[0]] += pos-prev

            prev = pos
            for is_enter, i in points[pos]:
                if is_enter:
                    heapq.heappush(min_heap, i)
                else:
                    exited[i] = True
        return result