题目
平面上有若干水平线段，现有一竖直直线扫描该平面，找到一个区间，使得该区间内与直线相交的线段最多。
分析
把线段投影到x轴上，问题可以转化为一维上的问题：在n个区间内找最多重合的区间。
思路
- 容易想到的解法：全局离散化
把所有点映射到数组里并初始化值为0，然后对每个区间里的每个点所映射的值进行+1，完成后扫描数组得到值最大的连续段即所求。
算法的问题在于：1.只能处理整型数据 2.需要但是浪费了太多的空间 - 解决存在的问题：map
很自然的，我们会想到用map来处理端点的映射而不是把所有点搬到数组里面，但这样又有一个新的问题：在只有端点信息的情况下，我们如何得到区间的信息呢？（面试中就卡这儿了:(((） - 一些编程技巧
假设一只蚂蚁爬过我们的x轴，经过左端点就捡起一粒芝麻，经过右端点之后就丢掉一粒芝麻，每个时刻蚂蚁拥有的芝麻数实际上就是我们要知道的区间信息，即重合度。有了这个关键的性质，再加上一点编程技巧，问题就比较好解决了。
求解过程
- 首先把所有的端点按大小升序排序， 用map存储<端点值，序号>
- 创建一个 size = 端点数量(不包含重复值)+1 的数组并初始化所有值为0
- 对每个 (start, end)有
++a[map[start]];
--a[map[end] +1]; // +一是因为经过末端点之后才能丢掉一颗芝麻- 完成后对做一个累加赋值，即 a[i]=a[0]+a[1]+...a[i]，这样数组中就存储了所有端点的重合度，我们只要找最大重合度的两个端点即完成求解
代码（java)
public class MaxIntervalOverlap {
public static void main(String[] args) {
try(
Scanner scanner = new Scanner(new File("MaxIntervalOverlap.data"))
){
/*
1.read input
*/
int M = scanner.nextInt();
int[] points = new int[2*M];
for (int i = 0; i < 2*M; i++) {
points[i] = scanner.nextInt();
}
/*
2.sort unique points to set
*/
Set<Integer> set = new TreeSet<>();
for(int point : points)
set.add(point);
/*
3.add to map
*/
Map<Integer, Integer> map = new HashMap<>();
int index = 0;
for(int point : set)
map.put(point, index++);
/*
4.go through all points
*/
int[] cover = new int[map.size() + 1];
for (int i = 0; i < points.length; i += 2) {
++cover[map.get(points[i])];
--cover[map.get(points[i + 1]) + 1];
}
/*
5.calculate cumulative sums
*/
int sum = 0;
int max = 0;
for (int i = 0; i < cover.length; i++) {
cover[i] = (sum += cover[i]);
if (cover[i] > max)
max = cover[i];
}
/*
6.get result int mapped array
*/
int startIndex = 0, endIndex = 0, maxLength = 0;
for (int i = 0; i < cover.length; i++) {
if (cover[i] == max){
if (startIndex == 0)
startIndex = i;
++maxLength;
}
}
endIndex = startIndex + maxLength - 1;
/*
7.retrieve result in original points
*/
int start = 0, end = 0;
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
if (entry.getValue() == startIndex)
start = entry.getKey();
else if (entry.getValue() == endIndex)
end = entry.getKey();
}
System.out.println("The maximum interval overlap is : " + max);
System.out.println("[" + start + ", " + end + "]");
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
}
总结
区间问题还有几个变种，关键点都与本问题类似，解法各不相同。但这种解法不仅很巧妙，还能求出其他变种问题需要的解，如最大重合度等。如果想看原回答地址请转至：原回答
