Skip to content

1943. Describe the Painting 👍

  • Time: $O(\texttt{sort} + n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
    vector<vector<long long>> ans;
    int prevIndex = 0;
    long runningMix = 0;
    map<int, long> timeline;

    for (const vector<int>& segment : segments) {
      const int start = segment[0];
      const int end = segment[1];
      const int color = segment[2];
      timeline[start] += color;
      timeline[end] -= color;
    }

    for (const auto& [i, mix] : timeline) {
      if (runningMix > 0)
        ans.push_back({prevIndex, i, runningMix});
      runningMix += mix;
      prevIndex = i;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<List<Long>> splitPainting(int[][] segments) {
    List<List<Long>> ans = new ArrayList<>();
    int prevIndex = 0;
    long runningMix = 0;
    TreeMap<Integer, Long> timeline = new TreeMap<>();

    for (int[] segment : segments) {
      final int start = segment[0];
      final int end = segment[1];
      final int color = segment[2];
      timeline.merge(start, (long) color, Long::sum);
      timeline.merge(end, (long) -color, Long::sum);
    }

    for (final int i : timeline.keySet()) {
      final long mix = timeline.get(i);
      if (runningMix > 0)
        ans.add(List.of((long) prevIndex, (long) i, runningMix));
      runningMix += mix;
      prevIndex = i;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from sortedcontainers import SortedDict


class Solution:
  def splitPainting(self, segments: list[list[int]]) -> list[list[int]]:
    ans = []
    prevIndex = 0
    runningMix = 0
    timeline = SortedDict()

    for start, end, color in segments:
      timeline[start] = timeline.get(start, 0) + color
      timeline[end] = timeline.get(end, 0) - color

    for i, mix in timeline.items():
      if runningMix > 0:
        ans.append([prevIndex, i, runningMix])
      runningMix += mix
      prevIndex = i

    return ans