题解 | 线段重合

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {



    // 定义全局的line和n 表示线段和线段的个数

    public static  int MaxN = 10001;// 题目说明N<= 10000
    public static int[][] line = new int[MaxN][2];
    public static int n;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int)in.nval;
            for (int i = 0;i < n;i++) {
                in.nextToken();
                line[i][0] = (int) in.nval;
                in.nextToken();
                line[i][1] = (int) in.nval;
            }
            out.println(compute());
        }
        out.flush();
        out.close();
        br.close();
    }


    public static int compute() {
        // 堆清空
        size = 0;
        Arrays.sort(line, 0, n, (a, b) -> a[0] - b[0]);
        int ans = 0;
        for (int i = 0;i < n;i++) {
            while (size > 0 && heap[0] <= line[i][0]) {
                pop();
            }
            add(line[i][1]);
            ans = Math.max(ans, size);
        }
        return ans;
    }


    // 堆
    public static int[] heap = new int[MaxN];

    // 堆的大小
    public static int size;

    // 增加一个节点，NlogN
    public static void add(int x) {
        heap[size] = x;
        int i = size++;
        while (heap[i]< heap[(i - 1) / 2]) {
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    public static void pop() {
        swap(0, --size);
        int i = 0, l = 1;
        while (l < size) {
            // 那个孩子更小，前提有右孩子
            int best = l + 1 < size  && heap[l + 1] < heap[l] ? l + 1 : l;
            best = heap[best] < heap[i] ? best : i;
            if (best == i) {
                break;// 已经是小根堆了
            }
            swap(i, best);
            i = best;
            l = 2 * i + 1;
        }

    }

    public static void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }






}