题解 | 线段重合

import java.util.Arrays;
import java.util.Scanner;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int MAX_N = 10001;
    public static int[][] line = new int[MAX_N][2];
    public static int n;
    // 小根堆，堆顶0位置
    public static int[] heap = new int[MAX_N];
    // 堆的大小
    public static int size;

    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]);
        // 先将线段按起始位置排升序 ---- 再将它们对应的结束位置放到小根堆里面去
        // 每次循环时加入一个结束位置，加入后比较堆顶的元素与新结束位置的开始位置，≤新，则弹出，直到堆中所有的元素都＞新。
        // 每次操作后需要调整堆，调整完成后，统计堆中元素，记录ans = MAX(size，ans)
        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(size, ans);
        }
        return ans;
    }

    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 = i * 2 + 1;
        }
    }

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

思路：既然一个线段和另一个线段重合，那么肯定是有一个线段的起始位置是重合区域的起始位置（可以自己画图看看）。有了这个结论，那么我们就只用比较A线段能不能在B线段内部或重合即可。我们可以先按照开始位置的大小进行升序排序，然后将它们对应的结束位置存到小根堆中。A线段能包含在B线段的情况有以下几种：

1. A-start＞B-start && A-end ＜ B-end

2. A-start = B -start && A - end ＜ B - end

3. A-start ＜ B-start && B-start ＜ A - end ＜ B-end。就这三种情况，我们可以看到其实就比对结束位置。因为我们是按照起始位置排序所以只会存在 A - START ≤ B - START ， 同时 A - END ＜ B - END。

所以我们将结束位置存到小根堆后，每次有新元素时，就需要比较新元素的起始位置是否大于堆顶元素。

每次操作都需要调整堆