青海工程建设云网站,免费自动生成小程序,oou淘宝客图片wordpress模板,百家利网站开发区间交集#xff1a;区间选点
区间选点
www.acwing.com/problem/content/907/ 可以参考区间合并的思路#xff0c;区间合并是求并集#xff0c;本题是求交集 正确性#xff1a;新的点应该尽可能的占有更多的区间#xff0c;那么就是求重叠最多的地方 实现角度#xf…区间交集区间选点
区间选点
www.acwing.com/problem/content/907/ 可以参考区间合并的思路区间合并是求并集本题是求交集 正确性新的点应该尽可能的占有更多的区间那么就是求重叠最多的地方 实现角度 如何记录重叠新加点后如何识别占有的区间 类似于区间合并但是每次都是收缩就能求出一段交集了
import java.util.*;public class Main {static final int N 100010;static Pair[] p new Pair[N];static int n;static class Pair implements ComparablePair {int l, r;public Pair(int l, int r) {this.l l;this.r r;}Overridepublic int compareTo(Pair o) {if (o.l l) {return r - o.r;}return l - o.l;}}public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();int l, r;for (int i 0; i n; i) {l sc.nextInt();r sc.nextInt();p[i] new Pair(l, r);}Arrays.sort(p, 0, n);l Integer.MAX_VALUE;r Integer.MIN_VALUE;int res 0;for (int i 0; i n; i) {if (r p[i].l) {res;l p[i].l;r p[i].r;} else {l p[i].l;r Math.min(r, p[i].r);}}System.out.println(res);}
}
