1. 问题描述
给定一些整数对（a，b）代表数轴上的两个点，且a<=b，这两个点表示一个线段。请返回最多几个线段重叠在一起。
例如：
- [[1,3],[2,5],[7,9]]，因为[1,3]和[2,5]重叠在一起，返回2；
- [[1,2],[2,3]]，返回2；
- [[1,2],[2,3],[1,3]]，返回3
- [[1,2]]，返回1
数组长度至少是1，不超过100_0000；
2. 暴力解法
2.1. 算法分析
我们可以用笔画几条线段发现，任何重叠的部分的左端点，都是某一个线段的左端点。比如[1,3]，和[2,4]重叠的部分是[2,3]，其中2就是第二个线段的左端点；又比如：[1,5]，[3,7]，[4,6]，重叠的部分是[4,5]，其中4就是[4,6]的左端点。既然任何一个重叠的部分都满足这个性质，那么重叠线段最多的那一部分，也满足。
因此我们只需要看一下，哪个左端点下经过的线段数目最多即可。
因此我们可以枚举所有线段的左端点，对于每一个左端点，再次枚举有几条线段经过当前点，返回最大值。
线段[a,b]经过当前点x的充要条件是：a<=x<=b
2.2. 代码
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
| public class MaxLineCoincide {
public static int maxLineCoincide(int[][] lines) {
int len = lines.length;
if(len == 1) return 1;
int ans = 1, t, leftPoint;
for(int i = 0; i < len; ++i) {
t=0;
leftPoint = lines[i][0];
for(int j=0; j<len; ++j) {
if(lines[j][0] <= leftPoint && leftPoint <= lines[j][1]) ++t;
}
ans = Math.max(t,ans);
}
return ans;
}
public static void main(String[] args) {
int[][] lines = {
{1,3},
{3,4}
};
System.out.println(maxLineCoincide(lines));
}
}
|
时间复杂度$O(N^2)$
3. 最优解
3.1. 算法分析
上述的解答中，最耗时的部分在于对于每一个左端点，找有几条线段通过这个点？因为给定的线段列表是杂乱的，因此我们只能遍历去找，浪费了时间。
如果我们把所有的线段，按照左端点从小到大排序，那么我们在确定一个左端点有几条线段通过它的时候，就可以排除一些不必要的遍历。
即对于一个左端点leftx，能通过它的线段，只可能是左端点不超过leftx的线段，如果一个线段的左端点都超过了leftx，那么这个线段是不会通过leftx的。
左端点不超过leftx的线段中，不都是满足条件的，只有那些右端点不小于leftx的线段，才是通过leftx的。因此我们还要知道这些线段的所有右端点信息，我们可以把这些线段的右端点都放在小跟堆中，不断从堆顶弹出一个右端点rightx，如果发现一个线段的右端点rightx，小于leftx，那么这个线段是不会计入leftx的答案的，当然在计算leftx的下一个（如果有的话）左端点nextLeftx的时候，更不会计入nextLeftx的答案，因此这个右端点rightx就丢弃了，直到某一个rightx不小于leftx的时候，因为是小跟堆，堆中所有的元素都是不小于leftx的，此时堆的size就是当前leftx的答案。
因此整体的算法如下：
- 把所有的线段，按照左端点从小到大排序
- 设置一个小跟堆，遍历每一个线段，对于每一个线段line：
- 把line的右端点rightx放入小跟堆；
- 只要堆顶元素小于当前线段的左端点leftx，则弹出
- 把堆此时的size作为子问题的答案，和全局答案pk
3.2. 代码
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
27
| import java.util.*;
public class MaxLineCoincide2 {
public static int maxLineCoincide(int[][] lines) {
int len = lines.length;
if(len == 1) return 1;
int ans = 1;
Arrays.sort(lines,(a,b)->a[0]-b[0]);
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i = 0; i < len; ++i) {
q.offer(lines[i][1]);
while(!q.isEmpty() && q.peek() < lines[i][0]) q.poll();
ans = Math.max(ans,q.size());
}
return ans;
}
public static void main(String[] args) {
int[][] lines = {
{1,3},
{3,4}
};
System.out.println(maxLineCoincide(lines));
}
}
|
时间复杂度$O(N\log_2N)$
4. 测试程序
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
27
28
29
30
31
32
33
| import java.util.*;
public class MaxLineCoincideTest {
public static void main(String[] args) {
int testTimes = 100_0000;
int maxArraySize = 100;
int maxPoint = 10_0000;
while(testTimes-- > 0) {
Random r = new Random();
int size = r.nextInt(maxArraySize) + 1;
int[][] data = new int[size][2], data2 = new int[size][2];
for(int i = 0; i < size; ++i) {
data[i][0] = r.nextInt(maxPoint);
data[i][1] = data[i][0] + r.nextInt(Integer.MAX_VALUE - data[i][0]);
data2[i][0] = data[i][0];
data2[i][1] = data[i][1];
}
int ans0 = MaxLineCoincide.maxLineCoincide(data);
int ans1 = MaxLineCoincide2.maxLineCoincide(data2);
if(ans0 != ans1) {
System.out.println("ans0: " + ans0 + " ans1: " + ans1);
for(int i = 0; i < size; ++i) {
System.out.println(Arrays.toString(data[i]));
}
throw new RuntimeException("Oops");
}
}
System.out.println("Done successfully!");
}
}
|
