专做女裤有哪些网站,中国版动漫网站模板,dw做的网站有什么缺陷,seo全站优化全案例区间合并#xff1a;区间合并问题
区间合并
www.acwing.com/problem/content/805/ 按区间的左端点排序 扫描整个区间#xff0c;在这过程中把可能有交点的区间合并 全包含#xff1a;不做改动相交#xff1a;right 后移相离#xff1a;更新至下一个维护区间
import j…区间合并区间合并问题
区间合并
www.acwing.com/problem/content/805/ 按区间的左端点排序 扫描整个区间在这过程中把可能有交点的区间合并 全包含不做改动相交right 后移相离更新至下一个维护区间
import java.util.*;public class Main {static final int N 100010;static Pair[] pairs new Pair[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 (this.l o.l) {return this.r - o.r;}return this.l - o.l;}} public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for (int i 0; i n; i) {int l sc.nextInt();int r sc.nextInt();pairs[i] new Pair(l, r);}Arrays.sort(pairs, 0, n);int result 1;int right pairs[0].r;for (int i 1; i n; i) {if (pairs[i].l right) {// 合并区间right Math.max(right, pairs[i].r);} else {// 新区间result;right pairs[i].r;}}System.out.println(result);}
}
