Problem URL: Describe the painting

We will loop over the segments and add the start and end points to a list. Then we will sort the list and loop over it. We will keep track of the current color and the current start point. When we reach a new color, we will add the current color and the current start point to the result. Then we will update the current color and the current start point.

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        mapping = collections.defaultdict(int)
        for start, end, cost in segments:
            mapping[start] += cost
            mapping[end] -= cost

        res = []
        prev, color = None, 0
        for now in sorted(mapping):
            if color:
                res.append((prev, now, color))
            color += mapping[now]
            prev = now

        return res

Time complexity: O(nlog(n))
Space complexity: O(n)