题解 | 撞车

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] sequence = new int[n][2];
        for (int i = 0; i < n; i++) {
            sequence[i][0] = in.nextInt();
            sequence[i][1] = in.nextInt();
        }
        Arrays.sort(sequence, (o1, o2) -> o1[0] - o2[0]);
        ArrayList<Integer> tailTable = new ArrayList<>();
        tailTable.add(sequence[0][1]);
        for (int i = 1; i < n; i++) {
            if (sequence[i][1] >= tailTable.get(tailTable.size() - 1)) {
                tailTable.add(sequence[i][1]);
            } else {
                int index = binarySearch(tailTable, sequence[i][1]);
                tailTable.set(index, sequence[i][1]);
            }
        }
        if (tailTable.size()==0){
            System.out.println(0);
        }else {
            System.out.println(n - tailTable.size());
        }
    }

    private static int binarySearch(ArrayList<Integer> tailTable, int val) {
        int low = 0, high = tailTable.size()    ;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (tailTable.get(mid) > val) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}