Java算法体系学习（五）堆的应用之最大线段重合问题

Java算法体系学习（五）堆的应用之最大线段重合问题 最大线段重合问题

• 给定很多线段，每个线段有两个整数[begin,end]，表示一条线段的起始位置和结束位置（end大于begin且都非负）
• 规定：重合区域必须大于等于1：例如[1,4]和[4,5]就不算重合
• 输入一个二维数组，数组的每个元素是一个包含两个元素的数组，分别为每个线段begin和end
• 返回线段最多重合区域中线段的个数
• 例如 arr = [[1,3],[2,4],[4,8]]
• 返回2,因为在[2,3]这个范围内有2个连段重合
• 思路：
  1. 先生成一个线段的类，包含begin和end两个数据
  2. 根据输入转化为线段类数组，并且把数组根据begin进行升序排序
  3. 建立一个线段类型小根堆，排序规则是根据放入线段的end进行排序
  4. 依次遍历数组，把堆中end位置小于等于当前遍历元素的begin都d出，当前堆中剩余元素就是经过当前begin位置的所有线段个数。因为堆中end小于begin的都为d出，所有end小于begin位置的元素肯定不经过begin位置。对数组进行排序是因为保证begin位置是从小到大的，这样能将所有的境况遍历完整。

package heap;


import sun.misc.InnocuousThread;

import java.util.Arrays;
import java.util.Comparator;

public class CoverMax {

    public static class Line{
        public int begin;
        public int end;

        public Line(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }
    }

    public static int coverMax(int[][] arr){
        int N = arr.length;
        Line[] lines = new Line[N];
        //生成线段数组
        for (int i = 0;i < N;i++){
            lines[i] = new Line(arr[i][0],arr[i][1]);
        }

        //将其根据begin位置进行排序
        Arrays.sort(lines, new Comparator() {
            @Override
            public int compare(Line o1, Line o2) {
                return o1.begin - o2.begin;
            }
        });

        //根据线段的end位置排序规则生成一个堆
        //其实不放line类型，直接用Integer放结束位置也可以
        HeapGreater heap = new HeapGreater<>(new Comparator() {
            @Override
            public int compare(Line o1, Line o2) {
                return o1.end - o2.end;
            }
        });

        //遍历每一个元素，把当前堆中小于begin的d出，堆中剩余元素就是经过begin位置的线段数量
        int max = 0;
        for (Line line : lines){
            while (!heap.isEmpty() && line.begin >= heap.peek().end){
                heap.pop();
            }
            heap.push(line);
            max = Math.max(max,heap.size());
        }
        return max;
    }

}