{x}
blog image

Describe the Painting

There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a unique color. You are given a 2D integer array segments, where segments[i] = [starti, endi, colori] represents the half-closed segment [starti, endi) with colori as the color.

The colors in the overlapping segments of the painting were mixed when it was painted. When two or more colors mix, they form a new color that can be represented as a set of mixed colors.

  • For example, if colors 2, 4, and 6 are mixed, then the resulting mixed color is {2,4,6}.

For the sake of simplicity, you should only output the sum of the elements in the set rather than the full set.

You want to describe the painting with the minimum number of non-overlapping half-closed segments of these mixed colors. These segments can be represented by the 2D array painting where painting[j] = [leftj, rightj, mixj] describes a half-closed segment [leftj, rightj) with the mixed color sum of mixj.

  • For example, the painting created with segments = [[1,4,5],[1,7,7]] can be described by painting = [[1,4,12],[4,7,7]] because:
    • [1,4) is colored {5,7} (with a sum of 12) from both the first and second segments.
    • [4,7) is colored {7} from only the second segment.

Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.

A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.

 

Example 1:

Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
Output: [[1,4,14],[4,7,16]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
- [4,7) is colored {7,9} (with a sum of 16) from the second and third segments.

Example 2:

Input: segments = [[1,7,9],[6,8,15],[8,10,7]]
Output: [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
Explanation: The painting can be described as follows:
- [1,6) is colored 9 from the first segment.
- [6,7) is colored {9,15} (with a sum of 24) from the first and second segments.
- [7,8) is colored 15 from the second segment.
- [8,10) is colored 7 from the third segment.

Example 3:

Input: segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
Output: [[1,4,12],[4,7,12]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,7} (with a sum of 12) from the first and second segments.
- [4,7) is colored {1,11} (with a sum of 12) from the third and fourth segments.
Note that returning a single segment [1,7) is incorrect because the mixed color sets are different.

 

Constraints:

  • 1 <= segments.length <= 2 * 104
  • segments[i].length == 3
  • 1 <= starti < endi <= 105
  • 1 <= colori <= 109
  • Each colori is distinct.

Solution Explanation

This problem involves processing a series of painting segments to determine the final painted result. Each segment has a start, end, and color. Overlapping segments mix their colors, and we need to represent the final painting using the minimum number of non-overlapping segments. The solution uses a line sweep algorithm with a TreeMap (or equivalent sorted map) to efficiently track color changes along the number line.

Algorithm:

  1. Event Tracking: We use a map to store events at each point on the number line. The keys represent the coordinates (start and end points of segments), and the values represent the change in the sum of colors at that coordinate. For each segment [start, end, color], we add color to the event at start and subtract color from the event at end. This technique effectively captures the color additions and removals at each point.

  2. Sorting Events: We sort the events by coordinate. This ensures we process the number line from left to right.

  3. Prefix Sum: We perform a prefix sum on the sorted events. This means we accumulate the changes in color sums to get the total color sum at each point.

  4. Outputting Segments: We iterate through the sorted events. When the cumulative color sum is greater than 0, it means that section is painted. We record the start of this painted section. When the cumulative color sum returns to 0, it indicates the end of a painted section; we then create a new segment using the start and end points we've recorded, along with the cumulative color sum.

Time and Space Complexity:

  • Time Complexity: O(N log N), dominated by sorting the events (where N is the number of segments). The prefix sum calculation and iteration through the sorted events take linear time.

  • Space Complexity: O(N), proportional to the number of unique coordinates on the number line that are either starts or ends of segments. In the worst-case scenario, each segment could have a unique start and end point.

Code Explanation (Python):

from collections import defaultdict
 
class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        d = defaultdict(int)  # Map to store events at each coordinate
        for l, r, c in segments:
            d[l] += c       # Add color at start
            d[r] -= c       # Subtract color at end
 
        s = sorted([[k, v] for k, v in d.items()])  # Sort events by coordinate
 
        n = len(s)
        for i in range(1, n): #Prefix sum calculation
            s[i][1] += s[i - 1][1]
 
        result = []
        for i in range(n - 1):  # Iterate through sorted events
            if s[i][1] > 0:  # Check if section is painted
                result.append([s[i][0], s[i + 1][0], s[i][1]]) #Create segment
 
        return result

The Java and C++ codes follow the same logic, using TreeMap and map respectively for efficient sorted storage of events. The core idea is the same across all languages. The prefix sum is implicitly calculated during the iteration in the Java and C++ solutions because the TreeMap / map already keeps the events sorted.