Describe the Painting

medium sweep line difference array sorting

Problem

A painting is a number line covered by overlapping half-closed segments [start, end), each with a unique color. Where colors overlap they mix into the sum of their colors. Return the minimum number of non-overlapping segments [left, right, mix) describing the finished painting, excluding any unpainted gaps.

Inputsegments = [[1,4,5],[4,7,7],[1,7,9]]

Output[[1,4,14],[4,7,16]]

[1,4) mixes {5,9} = 14; [4,7) mixes {7,9} = 16.

Inputsegments = [[1,7,9],[6,8,15],[8,10,7]]

Output[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]

Boundaries split the line into runs with constant color sum.

segments (start:end:color, comma-separated)

def split_painting(segments):
    diff = {}
    for start, end, color in segments:
        diff[start] = diff.get(start, 0) + color
        diff[end] = diff.get(end, 0) - color
    points = sorted(diff)
    res, running = [], 0
    for i in range(len(points) - 1):
        running += diff[points[i]]
        if running > 0:
            res.append([points[i], points[i + 1], running])
    return res

function splitPainting(segments) {
  const diff = new Map();
  for (const [start, end, color] of segments) {
    diff.set(start, (diff.get(start) || 0) + color);
    diff.set(end, (diff.get(end) || 0) - color);
  }
  const points = [...diff.keys()].sort((a, b) => a - b);
  const res = [];
  let running = 0;
  for (let i = 0; i < points.length - 1; i++) {
    running += diff.get(points[i]);
    if (running > 0)
      res.push([points[i], points[i + 1], running]);
  }
  return res;
}

List<List<Long>> splitPainting(int[][] segments) {
    TreeMap<Integer, Long> diff = new TreeMap<>();
    for (int[] s : segments) {
        diff.merge(s[0], (long) s[2], Long::sum);
        diff.merge(s[1], -(long) s[2], Long::sum);
    }
    List<List<Long>> res = new ArrayList<>();
    long running = 0;
    Integer prev = null;
    for (Map.Entry<Integer, Long> e : diff.entrySet()) {
        if (prev != null && running > 0)
            res.add(List.of((long) prev, (long) e.getKey(), running));
        running += e.getValue();
        prev = e.getKey();
    }
    return res;
}

vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
    map<int, long long> diff;
    for (auto& s : segments) {
        diff[s[0]] += s[2];
        diff[s[1]] -= s[2];
    }
    vector<vector<long long>> res;
    long long running = 0;
    int prev = 0; bool has = false;
    for (auto& [pt, d] : diff) {
        if (has && running > 0)
            res.push_back({prev, pt, running});
        running += d;
        prev = pt; has = true;
    }
    return res;
}

Explanation

This is a classic sweep line built on a difference map. Instead of tracking which colors cover every point, we only record where the total color sum changes.

For each segment [start, end, color] we add +color at start and -color at end. Because segments are half-closed [start, end), the color is active at start and inactive at end — exactly what these two deltas encode.

We then sort the distinct boundary points. Sweeping left to right, we keep a running sum of all deltas seen so far. Between point i and the next point i+1, that running sum is the constant mixed-color sum over the half-closed run [points[i], points[i+1]).

We emit a segment only when running > 0; a running sum of 0 means that stretch is unpainted, so we skip it. Adjacent runs with different sums stay separate, which guarantees the minimum number of segments because every emitted boundary is a real change in color.

Example: [[1,4,5],[4,7,7],[1,7,9]] gives deltas {1:+14, 4:+2, 7:-16}. Sweeping: run [1,4) has sum 14, run [4,7) has sum 16, and past 7 the sum is 0 — answer [[1,4,14],[4,7,16]].

Time: O(n log n) Space: O(n)