Medium
题目描述
有一幅长而细的画，可以用数轴来表示。这幅画是用多个重叠的线段绘制的，每个线段都用独特的颜色绘制。给你一个二维整数数组 segments，其中 segments[i] = [starti, endi, colori] 表示半闭区间 [starti, endi) 以 colori 作为颜色。
绘画时，重叠线段中的颜色会混合。当两种或多种颜色混合时，它们形成一种新颜色，可以表示为混合颜色的集合。
- 例如，如果颜色 2、4 和 6 混合，则结果混合颜色为
{2,4,6}。
为了简单起见，你应该只输出集合中元素的总和，而不是完整的集合。
你想用最少数量的非重叠半闭区间来描述这幅画的混合颜色。这些线段可以用二维数组 painting 表示，其中 painting[j] = [leftj, rightj, mixj] 描述了半闭区间 [leftj, rightj) 与混合颜色总和 mixj。
- 例如，用
segments = [[1,4,5],[1,7,7]]创建的绘画可以用painting = [[1,4,12],[4,7,7]]描述，因为：[1,4)被涂为{5,7}（总和为 12），来自第一和第二个线段。[4,7)被涂为{7}，仅来自第二个线段。
返回描述完成绘画的二维数组 painting（排除任何未绘制的部分）。你可以按任何顺序返回线段。
半闭区间 [a, b) 是数轴上点 a 和点 b 之间的部分，包括点 a 但不包括点 b。
示例 1：
输入：segments = [[1,4,5],[4,7,7],[1,7,9]]
输出：[[1,4,14],[4,7,16]]
解释：绘画可以描述如下：
- [1,4) 被涂为 {5,9}（总和为 14），来自第一和第三个线段。
- [4,7) 被涂为 {7,9}（总和为 16），来自第二和第三个线段。
示例 2：
输入：segments = [[1,7,9],[6,8,15],[8,10,7]]
输出：[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
示例 3：
输入：segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
输出：[[1,4,12],[4,7,12]]
约束：
1 <= segments.length <= 2 * 10^4segments[i].length == 31 <= starti < endi <= 10^51 <= colori <= 10^9- 每个
colori都是不同的。
解题思路
这道题的核心思路是利用差分数组和离散化技术来处理区间染色问题。
解题思路：
事件处理法：将每个线段的开始和结束看作事件，在开始位置加上颜色值，在结束位置减去颜色值。
离散化坐标：收集所有线段的起始和结束坐标，去重并排序，这样可以将连续的坐标映射到离散的点上。
扫描线算法：按坐标从小到大扫描，维护当前位置的颜色总和。当颜色总和发生变化时，说明需要创建一个新的区间。
构建结果：对于每个相邻的坐标对，如果该区间内有颜色（颜色总和不为0），则将其加入结果。
算法步骤：
- 创建事件列表：对每个线段，在起始位置添加颜色值，在结束位置减去颜色值
- 按坐标排序事件
- 扫描所有事件，维护当前颜色总和
- 当遇到新坐标且当前有颜色时，创建一个区间段
- 过滤掉颜色总和为0的区间（未染色区域）
这种方法的优势是能够高效处理重叠区间，时间复杂度为O(n log n)，其中n是线段数量。
代码实现
class Solution {
public:
vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
map<int, long long> events;
// 添加事件：开始位置+颜色，结束位置-颜色
for (auto& seg : segments) {
events[seg[0]] += seg[2];
events[seg[1]] -= seg[2];
}
vector<vector<long long>> result;
long long currentColor = 0;
int prevPos = -1;
for (auto& [pos, colorChange] : events) {
// 如果当前有颜色且不是第一个位置，添加区间
if (currentColor > 0 && prevPos != -1) {
result.push_back({prevPos, pos, currentColor});
}
currentColor += colorChange;
prevPos = pos;
}
return result;
}
};
class Solution:
def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
events = {}
# 添加事件：开始位置+颜色，结束位置-颜色
for start, end, color in segments:
events[start] = events.get(start, 0) + color
events[end] = events.get(end, 0) - color
result = []
current_color = 0
prev_pos = None
for pos in sorted(events.keys()):
# 如果当前有颜色且不是第一个位置，添加区间
if current_color > 0 and prev_pos is not None:
result.append([prev_pos, pos, current_color])
current_color += events[pos]
prev_pos = pos
return result
public class Solution {
public IList<IList<long>> SplitPainting(int[][] segments) {
var events = new SortedDictionary<int, long>();
// 添加事件：开始位置+颜色，结束位置-颜色
foreach (var seg in segments) {
events[seg[0]] = events.GetValueOrDefault(seg[0], 0) + seg[2];
events[seg[1]] = events.GetValueOrDefault(seg[1], 0) - seg[2];
}
var result = new List<IList<long>>();
long currentColor = 0;
int prevPos = -1;
foreach (var kvp in events) {
int pos = kvp.Key;
long colorChange = kvp.Value;
// 如果当前有颜色且不是第一个位置，添加区间
if (currentColor > 0 && prevPos != -1) {
result.Add(new List<long> { prevPos, pos, currentColor });
}
currentColor += colorChange;
prevPos = pos;
}
return result;
}
}
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 result = [];
let currentColor = 0;
let prevPos = null;
// 按位置排序
const sortedPositions = Array.from(events.keys()).sort((a, b) => a - b);
for (const pos of sortedPositions) {
// 如果当前有颜色且不是第一个位置，添加区间
if (currentColor > 0 && prevPos !== null) {
result.push([prevPos, pos, currentColor]);
}
currentColor += events.get(pos);
prevPos = pos;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | n为线段数量，主要耗时在事件排序 |
| 空间复杂度 | O(n) | 存储事件的哈希表空间 |