线段最大重合区域问题
作者：Grey
原文地址：
博客园：线段最大重合区域问题
CSDN：线段最大重合区域问题
题目描述
牛客-线段重合-连接点算重合区域
主要思路
暴力解法
第一步，首先得到所有线段开始位置的最小值（假设为 min）和结束位置的最大值（假设为 max)，组成了一个[min....max]区间；
第二步，在[min...max]区间内按单位 1 等分，对于每个等分位置的点，看看覆盖这个点的线段条数，最多线段覆盖的点，其线段条数就是答案。
完整代码如下
public static int maxCover3(int[][] lines) {
int min = lines[0][0];
int max = lines[0][1];
for (int[] line : lines) {
min = Math.min(min, Math.min(line[0], line[1]));
max = Math.max(max, Math.max(line[0], line[1]));
}
int cover = 0;
int maxCover = 0;
for (int i = min; i <= max; i++) {
for (int[] line : lines) {
// 这里要注意 如果[1,2] ,[2, 3] 中2 算一个重合点的话，
// 则条件为：line[0] <= i && line[1] >= i
// 如果不算的话，line[0] <= i+0.5 && line[1] >= i + 0.5
if (line[0] <= i && line[1] >= i) {
cover++;
}
}
maxCover = Math.max(cover, maxCover);
cover = 0;
}
return maxCover;
}
暴力解法时间复杂度O((max-min)*N)。
堆解法
准备小根堆，堆中存线段信息，遍历每一个线段，得到其开始位置 L 和结束位置 R，规则是：
- 每个线段按开始位置 L 从小到大排序；
- 如果堆为空，把线段结束位置 R 进入堆；
- 堆不为空，则遍历到线段 L 位置和堆顶元素(假设为 M )比较，如果堆顶元素小于 L，则结算一次堆中元素大小，记为 size，然后弹出堆顶元素，直到堆顶元素小于 L，然后把 L 加入；
- 每次生成的 size 取最大值即为最大重合了几个线段。
关键代码如下
public static int maxCover(int[][] lines) {
Arrays.sort(lines, Comparator.comparingInt(o -> o[0]));
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
int max = 0;
for (int[] line : lines) {
// 这里要注意
// 如果[1,2] ,[2, 3] 中2 算一个重合点的话，heap.peek()[1] < line[0]
// 如果不算的话，heap.peek()[1] <= line[0]
while (!heap.isEmpty() && heap.peek()[1] < line[0]) {
heap.poll();
}
heap.add(line);
max = Math.max(max, heap.size());
}
return max;
}
堆解法的时间复杂度是O(N*logN)。
线段树解法
主要思路如下：
第一步：先做离散化处理，这是线段树类型问题的常规操作；
// 离散化
public static HashMap<Integer, Integer> index(int[][] lines) {
TreeSet<Integer> set = new TreeSet<>();
for (int[] line : lines) {
set.add(line[0]);
set.add(line[1]);
}
HashMap<Integer, Integer> map = new HashMap<>(set.size());
int count = 0;
for (Integer i : set) {
map.put(i, ++count);
}
return map;
}
举例说明：
假设线段为[1,5]，[7,9]，[89,97]，[32,1077]，[2044,100039]，如果不做离散化处理，要覆盖的线段长度需要从 1 一直到 100039，浪费空间，所以，离散化以后，每个点映射关系如下
1 -> 1
5 -> 2
7 -> 3
9 -> 4
32 -> 5
89 -> 6
97 -> 7
1077 -> 8
2044 -> 9
100039 -> 10
线段就可以转换成
[1,5] -> [1,2]
[7,9] -> [3,4]
[89,97] -> [6,7]
[32,1077] -> [5,8]
[2044,100039] -> [9,10]
离散化的结果，得出的结论和原线段列表得出的结论是一样的。
第二步：离散化后，将每个线段的开始和结束位置加入线段数据；
第三步：在线段树原有逻辑的基础上，增加queryMax方法，用于计算重叠的区间个数，记录一个最大值即可。
线段树解法的完整代码如下，时间复杂度是O(N*logN):
// 线段树解法
public static int maxCover2(int[][] lines) {
HashMap<Integer, Integer> map = index(lines);
int N = map.size();
SegmentTree tree = new SegmentTree(N);
long max = 0;
for (int[] line : lines) {
int L = map.get(line[0]);
int R = map.get(line[1]);
tree.add(L, R, 1, 1, N, 1);
long l = tree.queryMax(L, R, 1, N, 1);
max = Math.max(l, max);
}
return (int) max;
}
// 离散化
public static HashMap<Integer, Integer> index(int[][] lines) {
TreeSet<Integer> set = new TreeSet<>();
for (int[] line : lines) {
set.add(line[0]);
set.add(line[1]);
}
HashMap<Integer, Integer> map = new HashMap<>(set.size());
int count = 0;
for (Integer i : set) {
map.put(i, ++count);
}
return map;
}
// [1...3],[2..6],[4..9]，问：哪个区间描的最多，可以用线段树(注意离散化，注意在范围内+1以后，执行的不是querySum而是queryMax)
// 注意：不管什么线段，开始位置排序，线段开始位置越早，越先处理
public static class SegmentTree {
private int MAXN;
private int[] arr;
private int[] max;
private int[] lazy;
public SegmentTree(int N) {
MAXN = N + 1;
arr = new int[MAXN];
int v = MAXN << 2;
lazy = new int[v];
max = new int[v];
}
private void pushUp(int rt) {
max[rt] = Math.max(max[rt << 1], max[(rt << 1) | 1]);
}
private void pushDown(int rt, int ln, int rn) {
if (lazy[rt] != 0) {
max[rt << 1] += lazy[rt];
max[(rt << 1) | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt];
lazy[(rt << 1) | 1] += lazy[rt];
lazy[rt] = 0;
}
}
public void add(int L, int R, int C, int l, int r, int rt) {
if (L <= l && R >= r) {
lazy[rt] += C;
max[rt] += C;
return;
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
add(L, R, C, mid + 1, r, (rt << 1) | 1);
}
pushUp(rt);
}
public long queryMax(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) {
return max[rt];
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
long left = Integer.MIN_VALUE;
long right = Integer.MIN_VALUE;
if (L <= mid) {
left = queryMax(L, R, l, mid, rt << 1);
}
if (R > mid) {
right = queryMax(L, R, mid + 1, r, (rt << 1) | 1);
}
return Math.max(left, right);
}
}
public static class Line {
public int start;
public int end;
public Line(int s, int e) {
start = s;
end = e;
}
}
类似问题
牛客-线段重合
主要思路：本题和上题唯一的区别就是：本题中的线段的连接点不算重合部分。思路和上题完全一样。
