給定 nn 個區間 [li,ri][li,ri]，要求合并所有有交集的區間，
注意如果在端點處相交，也算有交集，
輸出合并完成后的區間個數，
例如：[1,3]和[2,6]可以合并為一個區間[1,6]，
輸入格式
第一行包含整數n，
接下來n行，每行包含兩個整數 l 和 r，
輸出格式
共一行，包含一個整數，表示合并區間完成后的區間個數，
資料范圍
1≤n≤1000001≤n≤100000,
?109≤li≤ri≤109?109≤li≤ri≤109
輸入樣例：
5
1 2
2 4
5 6
7 8
7 9
輸出樣例：
3
思路：先按區間左端點排序；下一個區間和上一個區間有三種情況，在區間里，有交集，無交集，如下圖
代碼：
import java.util.*; class node implements Comparable<node>{ int l; int r; @Override public int compareTo(node o) { return this.l-o.l; } } public class Main{ static final int max=100005; static node p[]=new node[max]; public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); for(int i=0;i<n;i++){ p[i]=new node(); p[i].l=scan.nextInt(); p[i].r=scan.nextInt(); } Arrays.sort(p,0,n); int res=1,end=p[0].r; for(int i=1;i<n;i++){ if(p[i].l<=end) end=Math.max(end, p[i].r); else { res++; end=p[i].r; } } System.out.println(res); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103915.html
標籤：其他
上一篇：雙網卡設定問題（戴爾服務器）
下一篇：快速乘法模板