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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Describe the Painting

Number: 2055

Difficulty: Medium

Paid? No

Companies: spinny, Google

Problem Description

Given a list of painting segments where each segment is represented by a half-closed interval [start, end) with a unique color, overlapping segments mix their colors. The mixed color is represented as a set, but for simplicity, the output should be the sum of the colors in the set. The goal is to return the minimal list of non-overlapping segments with the correct summed mixed colors that form the final painting, excluding non-painted parts.

Key Insights

  • Use a sweep-line algorithm to process the segments as events.
  • For each segment, create two events: one for adding the color at the start and one for subtracting the color at the end.
  • Sort events by the coordinate to handle segments in order.
  • Accumulate the active colors sum while traversing through the events and record segments whenever the active sum changes.
  • Process all events occurring at the same coordinate together.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of events. Space Complexity: O(n) for storing the event list.

Solution

We use a sweep-line technique where each segment contributes two events (addition at the start and subtraction at the end). First, we sort all events by their coordinate. As we scan through the events, we maintain an active sum of colors. At each new coordinate, if the active sum is non-zero and the previous coordinate is different, we record the segment from the previous coordinate to the current coordinate with the current active sum. Finally, we update the active sum by processing all events at the current coordinate (all adds and subtracts). This produces the minimal set of non-overlapping segments that describe the painted intervals.

Code Solutions

# Python solution using sweep-line technique

def splitPainting(segments):
    # Create an empty list for events
    events = []
    # For each segment, add start and end events
    for start, end, color in segments:
        events.append((start, color))  # color is added at start
        events.append((end, -color))   # color is removed at end

    # Sort events by coordinate
    events.sort()
    
    # Initialize result list, active_color_sum and previous coordinate marker
    result = []
    active_sum = 0
    prev = None

    # Process each event
    i = 0
    n_events = len(events)
    while i < n_events:
        position, _ = events[i]
        # If prev is set and the current active sum is non-zero, add the interval to result
        if prev is not None and prev != position and active_sum != 0:
            result.append([prev, position, active_sum])
        
        # Process all events at the same position
        while i < n_events and events[i][0] == position:
            # Update active sum by adding the event's color delta
            active_sum += events[i][1]
            i += 1
        
        # Update previous coordinate to current position
        prev = position

    return result

# Example usage:
segments = [[1,4,5],[4,7,7],[1,7,9]]
print(splitPainting(segments))  # Expected output: [[1,4,14],[4,7,16]]
← Back to All Questions