905. 區間選點
思路
（貪心）O(nlogn)
根據右端點排序
-
將區間按右端點排序
-
遍歷區間，如果當前區間左端點不包含在前一個區間中，則選取新區間，所選點個數加1，更新當前區間右端點。如果包含，則跳過。
-
輸出所選點的個數。
舉例: 為什么不能根據左端點排序呢？
如下圖所示，有三個區間
我們按右側排序是如圖所示，l3 > r2，點數加1，更新右端點，l1 < l3，無需更新，直接跳過
如果改成按左側排序的話，r2 < r1 && r3 < r1,無需更新所需點數，輸出點數為1（錯誤）。
- 第一個區間為
l1~r1, 當我們遍歷到l2~r2的時候，沒有問題，l2 < r1, 無需更新。 - 但當我們遍歷到
l3~r3這個區間的話，就出現問題了，l3 < r1, 無需更新 - 輸出點數1
解決辦法 ：在遍歷其他區間的時候，同時更新區間右端點取最小值
Java代碼
import java.util.*;
class Range implements Comparable<Range>{int l,r;public Range(int l,int r){this.l = l;this.r = r;}public int compareTo(Range o){return Integer.compare(r,o.r);//return this.r - o.r;}
}
public class Main{static int N = 100010,INF = 0x3f3f3f3f,n;static Range[] range = new Range[N];//結構體創建數組需要定義成全局變量public static void main(String[] args){Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int l = scan.nextInt();int r = scan.nextInt();range[i] = new Range(l,r);}//結構體排序Arrays.sort(range,0,n); //Arrays.sort(range, 0, n, (o1, o2) -> o1.r - o2.r);int res = 0;//表示一共需要多少點int ed = -INF; // 上一個點的右端點for(int i = 0 ; i < n ; i ++ ){if(range[i].l > ed){res ++ ;ed = range[i].r;}}System.out.println(res);}
}
根據左端點排序
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();List<Pair> v = new ArrayList<>();for(int i = 0; i < n; i ++) {int l = sc.nextInt();int r = sc.nextInt();v.add(new Pair(l, r));}Collections.sort(v, (a, b) -> a.x - b.x);int l = Integer.MIN_VALUE;int r = Integer.MIN_VALUE;int res = 0;for(Pair p : v) {if(p.x <= r) {// l = Math.max(l, p.x);r = Math.min(r, p.y); (每次取r的最小值，本質上其實還是根據右端點進行排序)} else {res += 1;l = p.x;r = p.y;}}System.out.println(res);}}class Pair implements Comparable<Pair> {int x;int y;public Pair(int x, int y) {this.x = x;this.y = y;}@Overridepublic int compareTo(Pair o) {return Integer.compare(this.x, o.x);}
}
正確性證明 ：
定義：Ans 為所有可行方案中所需點最小數量，Cnt為當前方案中所需點的數量(一種可行方案)
-
為證明 Ans == Cnt ，我們只需證明 Ans >= Cnt , Ans <= Cnt即可。
-
既然Ans為最小數量，易得Ans <= Cnt。
-
由于我們是根據右端點進行排序遍歷，舉一個極端例子，由圖可知，Cnt等于4，Ans >= 4。
-
Ans >= Cnt &&Ans <= Cnt -> Ans = Cnt。
