Problem Description

You are given a list of segments, where each segment is represented as an array [start, end, color]. Each segment paints the interval from start (inclusive) to end (exclusive) with the given color. If multiple segments overlap, the colors are combined (summed) for the overlapping parts.

Your task is to describe the final painting as a list of non-overlapping intervals, where each interval is represented as [start, end, totalColor]. Here, totalColor is the sum of all colors covering that interval. The intervals should be sorted in increasing order of start and should not overlap.

Constraints:

• Each segment is [start, end, color] with start < end
• No two segments are identical
• All input values are positive integers

Thought Process

At first glance, the problem looks like a classic interval merging or "sweep line" problem. The brute-force approach would be to create an array for every possible point, sum the colors at each position, and then combine contiguous parts with the same color sum. However, this would be slow and memory-intensive for large ranges.

Instead, we realize that the only points where the total color changes are the segment endpoints. So, we can focus on changes at these points, using a sweep line approach: as we process left-to-right, we add or remove colors at each endpoint, and whenever the total color changes, we record a new interval.

This optimization reduces both time and space, since we only process at most twice as many events as there are segments.

Solution Approach

• Step 1: Collect Events
  • For each segment [start, end, color], record two events:
  • At start, add color to the total
  • At end, subtract color from the total
• Step 2: Sort Events
  • Sort all events by position (start/end). If multiple events occur at the same point, process additions before subtractions.
• Step 3: Sweep Line Processing
  • Initialize curr_color = 0 and prev_pos = None
  • Iterate through all events in order:
  • If curr_color > 0 and prev_pos != pos, record interval [prev_pos, pos, curr_color]
  • Update curr_color by adding/subtracting the event's color
  • Set prev_pos to current pos
• Step 4: Return Result
  • Return the list of recorded intervals, ensuring all intervals are non-overlapping and sorted.

This approach is efficient because it only processes the points where changes actually occur, and uses a simple running total to track the color sum.

Example Walkthrough

Suppose the input is segments = [[1,4,5], [4,7,7], [1,7,9]].

• Events:
  • (1, +5), (4, -5) from [1,4,5]
  • (4, +7), (7, -7) from [4,7,7]
  • (1, +9), (7, -9) from [1,7,9]
• All events: (1, +5), (1, +9), (4, -5), (4, +7), (7, -7), (7, -9)
• Sort by position: (1, +5), (1, +9), (4, -5), (4, +7), (7, -7), (7, -9)
• Sweep:
  • At 1: curr_color = 0 + 5 = 5; then +9 = 14
  • Interval [1,4] with color 14
  • At 4: curr_color = 14 - 5 = 9; then +7 = 16
  • Interval [4,7] with color 16
  • At 7: curr_color = 16 - 7 = 9; then -9 = 0
  • Painting ends at 7
• Final intervals: [[1,4,14], [4,7,16]]

Time and Space Complexity

• Brute-force approach:
  • Time: O(max_range * n), where max_range is the largest point painted and n is the number of segments
  • Space: O(max_range)
• Optimized sweep line approach:
  • Time: O(n log n), since we sort 2n events and process them all in one pass
  • Space: O(n), for storing events and the result
• This is a big improvement, especially for large or sparse intervals.

Summary

The key insight is that the only interesting points are where the color sum changes: segment starts and ends. By turning the problem into a sweep line algorithm, we efficiently compute the result in O(n log n) time and O(n) space, without unnecessary brute-force enumeration. This method is both elegant and practical for interval summing and merging problems.

Code Implementation

class Solution:
    def splitPainting(self, segments):
        from collections import defaultdict
        events = defaultdict(int)
        for start, end, color in segments:
            events[start] += color
            events[end] -= color
        res = []
        curr_color = 0
        prev = None
        for pos in sorted(events):
            if prev is not None and curr_color != 0:
                res.append([prev, pos, curr_color])
            curr_color += events[pos]
            prev = pos
        return res
      

class Solution {
public:
    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
        map<long long, long long> events;
        for (auto& seg : segments) {
            events[seg[0]] += seg[2];
            events[seg[1]] -= seg[2];
        }
        vector<vector<long long>> res;
        long long curr = 0, prev = -1;
        for (auto& [pos, val] : events) {
            if (prev != -1 && curr != 0) {
                res.push_back({prev, pos, curr});
            }
            curr += val;
            prev = pos;
        }
        return res;
    }
};
      

class Solution {
    public List<List<Long>> splitPainting(int[][] segments) {
        TreeMap<Long, Long> events = new TreeMap<>();
        for (int[] seg : segments) {
            events.put((long)seg[0], events.getOrDefault((long)seg[0], 0L) + seg[2]);
            events.put((long)seg[1], events.getOrDefault((long)seg[1], 0L) - seg[2]);
        }
        List<List<Long>> res = new ArrayList<>();
        long curr = 0, prev = -1;
        for (long pos : events.keySet()) {
            if (prev != -1 && curr != 0) {
                res.add(Arrays.asList(prev, pos, curr));
            }
            curr += events.get(pos);
            prev = pos;
        }
        return res;
    }
}
      

var splitPainting = function(segments) {
    const events = new Map();
    for (const [start, end, color] of segments) {
        events.set(start, (events.get(start) || 0) + color);
        events.set(end, (events.get(end) || 0) - color);
    }
    const keys = Array.from(events.keys()).sort((a, b) => a - b);
    const res = [];
    let prev = null, curr = 0;
    for (const pos of keys) {
        if (prev !== null && curr !== 0) {
            res.push([prev, pos, curr]);
        }
        curr += events.get(pos);
        prev = pos;
    }
    return res;
};