题解 | 撞车

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.function.Function;

/**
 * @author supermejane
 * @date 2025/10/8
 * @description BGN67 撞车
 */
public class Main {
	
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] a = new int[n][2];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            a[i][0] = in.nextInt();
            a[i][1] = in.nextInt();
        }

        Arrays.sort(a, (o1, o2) -> {
            if (o1[0] == o2[0]) return 0;
            return o1[0] > o2[0] ? 1 : -1;
        });
	  
//		  使用dp为o(n * n)会超时
//        int subLength = 0;
//        Arrays.fill(dp, 1);
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (illegal(a, i, j)) {
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//                }
//            }
//            subLength = Math.max(subLength, dp[i]);
//        }
//        System.out.println(n - subLength);


//        System.out.println(lis(((Function<int[][], int[]>) ab -> Arrays.stream(ab).mapToInt(e -> e[1]).toArray()).apply(a)));
        System.out.println(n - ldns(Arrays.stream(a).mapToInt(e -> e[1]).toArray()));
    }

//    其实就是 最长非递减子序列（Longest Non-Decreasing Subsequence, LNDS
//    public static boolean illegal(int[][] a, int i, int j) {
//        if (i <= j || a[i][0] < a[j][0]) throw new RuntimeException("错误的参数");
//        if (a[i][1] >= 0) return a[j][1] <= 0 || a[j][1] <= a[i][1];
//        else return a[j][1] <= a[i][1];
//        return a[i][1] >= 0 ? a[j][1] <= 0 || a[j][1] == a[i][1] : a[j][1] == a[i][1];
//    }

    //使用贪心 + 二分的方式求ldns, 为o(n * log(n))
    public static int ldns(int[] a) {
        int[] b = new int[a.length];
        int cnt = -1;
        for (int i = 0; i < a.length; i++) {
            if (cnt < 0 || a[i] >= b[cnt]) b[++cnt] = a[i];
            else {
                //二分查找大于a[i]的元素的位置
                int l = 0, r = cnt;
                while (r > l) {
                    int mid = (r - l) / 2 + l;
                    if (b[mid] <= a[i]) l = mid + 1;
                    else r = mid;
                }
                if (b[l] <= a[i]) System.out.println("Not Found.");
                b[l] = a[i];
            }
        }
        return cnt + 1;
    }

    public static int binary(int[] a, int target) {
        int l = 0, r = a.length - 1;
        while (r > l) {
            int mid = (r - l) / 2 + l;
            if (a[mid] <= target) l = mid + 1;
            else r = mid;
        }
        return a[l] > target ? l : -1;
    }
}

//一开始用的dp超时，就像可不可以预处理把for j的循环预处理减为o(1), 但是好像没有办法，后面看了题解才知道ldns还有o(n * log(n))的方法求解