We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Describe the Painting

Difficulty: Medium

Problem Description

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] = [start_i, end_i, color_i] represents the half-closed segment [start_i, end_i) with color_i 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 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. Return the 2D array painting describing the finished painting (excluding any parts that are not painted).

Key Insights

  • Each segment is defined by a unique start and end point, with a specific color.
  • Overlapping segments can result in mixed colors, represented as a sum of distinct colors within the overlaps.
  • The goal is to consolidate overlapping segments into non-overlapping segments while preserving the sum of mixed colors.
  • The problem can be visualized as merging intervals and tracking color contributions at each point.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the segments by their start points. Space Complexity: O(n) for storing the results and auxiliary data structures.

Solution

To solve the problem, we can use a sorting approach combined with a sweep line technique:

  1. First, we sort the segments based on their start position.
  2. We initialize a list to hold the resulting segments and a variable to track the current end of the merged segment.
  3. We use a map to track the sum of colors in the current overlapping segments as we iterate through the sorted segments.
  4. For each segment, if it overlaps with the current segment, we update the sum of colors. If it does not, we finalize the current segment and start a new one.
  5. The resulting segments will be constructed based on the distinct color sums for the corresponding ranges.

Code Solutions

def describePainting(segments):
    events = []
    for start, end, color in segments:
        events.append((start, color, 1))  # start of a segment
        events.append((end, color, -1))    # end of a segment

    events.sort()  # Sort events by position

    current_colors = {}  # Maps color to its count
    last_position = -1
    result = []

    for position, color, action in events:
        if last_position != -1 and current_colors:
            # Calculate the sum of current colors
            color_sum = sum(current_colors.keys())
            result.append([last_position, position, color_sum])

        # Update the current_colors based on the action
        if action == 1:  # Starting segment
            current_colors[color] = current_colors.get(color, 0) + 1
        else:  # Ending segment
            if color in current_colors:
                del current_colors[color]

        last_position = position

    return result
← Back to All Questions