Describe the Painting

Problem (yeniden ifade)

Renkli yarı-açık parçalar [start, end). Örtüşmeler renkleri karıştırır (toplam). Rengin sabit ve sıfır olmadığı örtüşmeyen karışık parçaları [left, right, colorSum] olarak döndür.

Sezgi

Uç noktalarda olaylar: start’ta +color, end’te -color. Sıralı konumları süpür; ardışık olaylar arasında toplam ≠ 0 ise yaz.

Yaklaşımlar

export function splitPainting(segments: number[][]): number[][] {
  const diff = new Map<number, number>();
  for (const s of segments) {
    diff.set(s[0]!, (diff.get(s[0]!) ?? 0) + s[2]!);
    diff.set(s[1]!, (diff.get(s[1]!) ?? 0) - s[2]!);
  }
  const keys = [...diff.keys()].sort((a, b) => a - b);
  const res: number[][] = [];
  let cur = 0;
  let prev = -1;
  for (const x of keys) {
    if (prev !== -1 && cur !== 0) res.push([prev, x, cur]);
    cur += diff.get(x)!;
    prev = x;
  }
  return res;
}

export function splitPainting(segments: number[][]): number[][] {
  const diff = new Map<number, number>();
  for (const s of segments) {
    diff.set(s[0]!, (diff.get(s[0]!) ?? 0) + s[2]!);
    diff.set(s[1]!, (diff.get(s[1]!) ?? 0) - s[2]!);
  }
  const keys = [...diff.keys()].sort((a, b) => a - b);
  const res: number[][] = [];
  let cur = 0;
  let prev = -1;
  for (const x of keys) {
    if (prev !== -1 && cur !== 0) res.push([prev, x, cur]);
    cur += diff.get(x)!;
    prev = x;
  }
  return res;
}

Şablon bağlantısı

Difference array / sweep-line olayları.

Yansıma

• Renkler seyrek uçlarda toplanır. Aynı konumda biten ve başlayan segmenti neden tek olayda birleştirirsin?
• Karışım 0 olunca boya biter. Ardışık aynı karışımı neden tek parça yazarsın?
• Renk 0 eklemek veya boş aralık çıktıyı bölmemeli. Sıra, koordinata göre.