题解 | 撞车

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       //贪心+排序+动态规划
       //速度正负数分别表示两个方向
       //两辆车某一时刻处于同一个位置会发生碰撞
       //碰撞条件1.它们朝对方运动或同向但后车更快，并且后车能追上或相向而行相遇
       //静止的车有车朝它开过来 → 会撞上
       //最长不碰撞子序列,所有车按位置x从小到大排序速度非递减排序
       int n=in.nextInt();
       int[][]cars=new int[n][2];
       for(int i=0;i<n;i++){
        cars[i][0]=in.nextInt();
        cars[i][1]=in.nextInt();
       }
        //按位置排序
        Arrays.sort(cars,(a,b)->Integer.compare(a[0],b[0]));
        //求数组最长非递减子序列
        List<Integer>list=new ArrayList<>();
        for(int i=0;i<n;i++){
            int v=cars[i][1];
            int l=0,r=list.size();
            while(l<r){
                int mid=(l+r)/2;
                //找第一个>=v的元素
               if(list.get(mid)<=v){
                l=mid+1;
               }else{
                r=mid;
               }
            }
            if(l==list.size()){
                list.add(v);
            }else{
                //把l位置的值改成v
                list.set(l,v);
            }
        }
        System.out.println(n-list.size());
    }
}