题目

平面上有若干水平线段，现有一竖直直线扫描该平面，找到一个区间，使得该区间内与直线相交的线段最多。

分析

把线段投影到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();
    }
}
}