LeetCode Solutions Blog

Amount of New Area Painted Each Day

Number: 2297

Difficulty: Hard

Paid? Yes

Problem Description

You are given a list of intervals where each interval [start, end) represents a segment on a number line that must be painted on a specific day. The twist is that if an area has already been painted on a previous day, painting it again does not count as "new" work. For each day, determine the length of the segment that is painted for the first time.

Key Insights

The problem requires merging intervals and computing the “gap” (or uncovered region) within the current interval that hasn’t been painted before.
We can maintain a collection of already painted intervals (as merged disjoint segments). For each new interval, we only add the parts that are not covered by any existing intervals.
Using an ordered data structure (balanced tree, sorted list, or ordered set) helps efficiently query and merge overlapping intervals.
The challenge is merging intervals on the fly and keeping track of “new” painted segments without double counting.

Space and Time Complexity

Time Complexity: O(n log n) on average, since each insertion and search in the ordered interval set takes logarithmic time and merging is efficient due to non-overlapping intervals. Space Complexity: O(n), for storing the merged intervals.

Solution

We maintain a sorted list (or ordered set) of disjoint intervals that have already been painted. For each day's paint interval [L, R):

Query the current collection to find all intervals that overlap with [L, R).
Compute the length of the uncovered segments inside [L, R) by iterating over the overlapping intervals and summing gaps.
Merge the overlapping intervals with the new paint interval to update the painted intervals.
Record the new painted length. This ensures that overlapping areas are only counted once and that the data structure always reflects the union of all painted intervals so far.

Code Solutions

# Python solution using a sorted list to maintain disjoint intervals
class Solution:
    def amountPainted(self, paint):
        # List to store disjoint painted intervals; each interval is [start, end)
        mergedIntervals = []
        ans = []
        
        # Iterate over each day's paint interval [L, R)
        for L, R in paint:
            newArea = 0
            # Use temporary variables for merging the current interval with overlaps
            newL, newR = L, R
            temp = []
            i = 0
            # Append intervals that end before the current interval starts (no overlap)
            while i < len(mergedIntervals) and mergedIntervals[i][1] < L:
                temp.append(mergedIntervals[i])
                i += 1
                
            # For overlapping intervals, count gaps and merge intervals
            cur = L  # pointer to track end of the last covered segment within [L, R)
            while i < len(mergedIntervals) and mergedIntervals[i][0] <= R:
                # mergedIntervals[i] overlaps with [L, R)
                start, end = mergedIntervals[i]
                # If there is a gap from current pointer to the start of this interval, add it
                if start > cur:
                    newArea += start - cur  # gap that is not covered
                # Move the pointer to the farthest painted point
                cur = max(cur, end)
                # Merge the current interval with the overlapping interval
                newL = min(newL, start)
                newR = max(newR, end)
                i += 1
                
            # If there is a gap after the last overlapping interval, add that gap length
            if cur < R:
                newArea += R - cur
                
            # Add the merged interval for the current day's paint operation
            temp.append([newL, newR])
            
            # Append remaining intervals after the current overlapping set
            while i < len(mergedIntervals):
                temp.append(mergedIntervals[i])
                i += 1
            
            # Update the merged intervals list
            mergedIntervals = temp
            # Append result for current day
            ans.append(newArea)
        
        return ans

# Example usage:
# sol = Solution()
# print(sol.amountPainted([[1,4],[4,7],[5,8]]))  # Expected output: [3,3,1]