网站开发服务器sem搜索引擎营销

区间交集：区间选点

区间选点

www.acwing.com/problem/content/907/

1. 可以参考区间合并的思路，区间合并是求并集，本题是求交集

2. 正确性：新的点应该尽可能的占有更多的区间，那么就是求重叠最多的地方

3. 实现角度：

   1. 如何记录重叠
   2. 新加点后如何识别占有的区间

4. 类似于区间合并，但是每次都是收缩，就能求出一段交集了

import java.util.*;public class Main {static final int N = 100010;static Pair[] p = new Pair[N];static int n;static class Pair implements Comparable<Pair> {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);}
}