题解 | 撞车

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int a[][]=new int[n][2];
		for (int i = 0; i < a.length; i++) {
			a[i][0]=scanner.nextInt();
			a[i][1]=scanner.nextInt();
		}
		Arrays.sort(a,(c,b)->(c[0]-b[0]));//给二维数组根据位置排序
		int v[]=new int[n+1];
		for (int i = 1; i <= n; i++) {
			v[i]=a[i-1][1];//把速度提取出来
		}
		//二分＋贪心
		ArrayList<Integer> list=new ArrayList<>();
		list.add(v[1]);
		for (int i = 2; i < v.length; i++) {
			if(v[i]>=list.get(list.size()-1)) {
				list.add(v[i]);//大于等于直接加在后面
			}else {
				//小于就替换第一个大于v[i]的数
				//使用二分
				int l=0;int r=list.size()-1;
				while(l<r) {
					int m=(l+r)/2;
					if(list.get(m)<=v[i]) {
						l=m+1;
					}else {
						r=m;
					}
				}
				//结束以后l索引的值就是第一个大于v[i]的值
				list.set(l, v[i]);//set替换，将指定索引的值用新给的值替换
				
			}
		}
		int len=list.size();
		System.out.println(n-len);
		

	}

}

这里n的取值有10的5次方，不难使用传统的动态规划，会超时，我们应该采用二分＋贪心的思路来优化，创建一个集合，来装每一个长度结束时的值，如果v[i]大于等于该值，就直接把该值加到集合后面，反之，我们就采取优化，把第一个大于v[i]的值用v[i]替换掉。