905. 區(qū)間選點(diǎn)

思路

（貪心）O(nlogn)

根據(jù)右端點(diǎn)排序

1. 將區(qū)間按右端點(diǎn)排序

2. 遍歷區(qū)間，如果當(dāng)前區(qū)間左端點(diǎn)不包含在前一個(gè)區(qū)間中，則選取新區(qū)間，所選點(diǎn)個(gè)數(shù)加1，更新當(dāng)前區(qū)間右端點(diǎn)。如果包含，則跳過。

3. 輸出所選點(diǎn)的個(gè)數(shù)。

舉例: 為什么不能根據(jù)左端點(diǎn)排序呢？

如下圖所示，有三個(gè)區(qū)間

我們按右側(cè)排序是如圖所示，l3 > r2，點(diǎn)數(shù)加1，更新右端點(diǎn)，l1 < l3，無需更新，直接跳過

如果改成按左側(cè)排序的話，r2 < r1 && r3 < r1,無需更新所需點(diǎn)數(shù)，輸出點(diǎn)數(shù)為1（錯(cuò)誤）。

• 第一個(gè)區(qū)間為l1~r1, 當(dāng)我們遍歷到l2~r2的時(shí)候，沒有問題，l2 < r1, 無需更新。
• 但當(dāng)我們遍歷到l3~r3這個(gè)區(qū)間的話，就出現(xiàn)問題了，l3 < r1, 無需更新
• 輸出點(diǎn)數(shù)1

解決辦法 ：在遍歷其他區(qū)間的時(shí)候，同時(shí)更新區(qū)間右端點(diǎn)取最小值

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];//結(jié)構(gòu)體創(chuàng)建數(shù)組需要定義成全局變量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);}//結(jié)構(gòu)體排序Arrays.sort(range,0,n); //Arrays.sort(range, 0, n, (o1, o2) -> o1.r - o2.r);int res = 0;//表示一共需要多少點(diǎn)int ed = -INF; // 上一個(gè)點(diǎn)的右端點(diǎn)for(int i = 0 ; i < n ; i ++ ){if(range[i].l > ed){res ++ ;ed = range[i].r;}}System.out.println(res);}
}

根據(jù)左端點(diǎn)排序

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的最小值，本質(zhì)上其實(shí)還是根據(jù)右端點(diǎn)進(jìn)行排序)} 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 為所有可行方案中所需點(diǎn)最小數(shù)量，Cnt為當(dāng)前方案中所需點(diǎn)的數(shù)量(一種可行方案)

1. 為證明 Ans == Cnt ，我們只需證明 Ans >= Cnt , Ans <= Cnt即可。

2. 既然Ans為最小數(shù)量，易得Ans <= Cnt。

3. 由于我們是根據(jù)右端點(diǎn)進(jìn)行排序遍歷，舉一個(gè)極端例子，由圖可知，Cnt等于4，Ans >= 4。

4. Ans >= Cnt &&Ans <= Cnt -> Ans = Cnt。