Describe the painting

Array Hash Table Sorting Prefix Sum

52.0% acceptance

Feb 25, 2026

550

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 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. Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeMap;

impl Solution {
  pub fn split_painting(segments: Vec<Vec<i32>>) -> Vec<Vec<i64>> {
    let mut events: BTreeMap<i32, i64> = BTreeMap::new();
    for seg in &segments {
      *events.entry(seg[0]).or_insert(0) += seg[2] as i64;
      *events.entry(seg[1]).or_insert(0) -= seg[2] as i64;
    }

    let mut result = Vec::new();
    let mut cur_sum: i64 = 0;
    let mut prev_pos = 0;

    for (&pos, &delta) in &events {
      if cur_sum > 0 && prev_pos < pos {
        result.push(vec![prev_pos as i64, pos as i64, cur_sum]);
      }
      cur_sum += delta;
      prev_pos = pos;
    }
    result
  }
}