按照區間左端點從?到?排序，當兩個區間「重疊」的時候，我們必須要舍棄?個。為了能夠「在移除某個區間后，保留更多的區間」，我們應該把「區間范圍較?」的區間移除。
因此以第?個區間為基準，遍歷所有的區間：

• 如果重疊，選擇「最?的右端點」作為新的基準；
• 如果不重疊，那么我們就能多選?個區間，以「新區間為基準」繼續向后遍歷。

可以?「交換論證法」證明我們的貪?策略是最優解：
在從前往后掃描的過程中，當貪?解和最優解第?次出現不同決策時，關于兩個區間a,b（其中a在左，b在右）的取舍，有下?兩種情況：

1. a, b兩個區間不重疊：

• 貪?解會將a 區間保留，然后以b 區間為基準，繼續向后對?別的區間；
• 最優解的選擇有下??種情況：
  a. 舍棄?個區間，那么必定不如貪?解，?盾。
  b. 以a區間為基準，向后對?。那更夸張了，我們已經按照區間左端點從?到?排好序了，如果a,b不重疊，那么a與后?的所有區間都不重疊，?a作為基準沒有?點意義。還會選出與b重疊的區間。
  綜上，如果「不重疊」的話，貪?解和最優解的決策應該是「?致」的。

1. a, b 兩個區間重疊，那么?論什么解，都需要「舍棄」?個區間：

• 貪?解會保留兩者「右端點較?」的區間，舍棄「右端點較?」的區間；
• 最優解的選擇就是，保留「右端點較?」的區間，舍棄「右端點較?」的區間。
  如果第?種決策能在此基礎上得到最優解，那么我們把「右端點較?」區間換成「右端點較?」的區間是不受影響的。
  因為「較?區間」都和后續選擇的區間「沒有重疊」，這個較?的區間也必定「沒有重疊」。因此，最優解可以調整成貪?解。

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int n;
struct node
{int l, r;
}a[N];bool cmp(node& x, node& y)
{return x.l < y.l;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;sort(a+1, a+1+n, cmp);int ret = 1;int r = a[1].r; //以第一個區間為基準for (int i = 2; i <= n; i++){int left = a[i].l, right = a[i].r;if (left < r) //有重疊{r = min(r, right);}else{ret++;r = right;}}cout << ret << endl;return 0;
}

如圖所?，當?個島嶼的「坐標」已知，其實可以計算出：當雷達放在x軸的「哪段區間」時，可以覆蓋到這個島嶼

根據「勾股定理」得：ax的?度為$l=\sqrt{d^2?y^2}$，那么雷達所處的范圍就是$[x?l,x+l]$。因此，針對每?個島嶼，我們都可以算出?個「能夠覆蓋它的區間」。
原問題就變成給定?些區間，所有互相重疊的區間?共有多少組。
按照區間「左端點從?到?」排序，當兩個區間「重疊」的時候，為了后?能夠「盡可能多的選出互相重疊的區間」，我們應該把「區間范圍較?」的區間移除，因為選擇較?區間會造成選出來的區間「不是互相重疊」的。
因此以第?個區間為基準，遍歷所有的區間：

• 如果重疊，選擇「最?的右端點」作為新的基準；
• 如果不重疊，那么我們就能多選?個區間，以「新區間為基準」繼續向后遍歷。
  可以?「反證法」證明，所有區間按照按照「左端點」排序之后，「互相重疊的區間」都是「相鄰」的：
  假設所有區間按照左端點排序之后，存在互相重疊的區間，它們是不相鄰的。也就是存在a,b,c,d四個區間，其中a,b,d互相重疊，但是a,b,c與它們三個不是互相重疊。
  設a, b, d區間重疊部分的范圍是[x, y]，那么c 的位置有兩種情況：
• c 在[x, y]的左側，與實際不符：
  因為如果c在左側，?要與a,b不是互相重疊，那么c的右端點必須要?于b的左端點，那就與所有線段按照左端點排序不符；
• c 在[x, y]的右側，也與實際不符：
  因為如果c在右側，?要與a,b不是互相重疊，那么c的左端點必須要?于a,b的右端點的最?值；?因為d與a,b互相重疊，d的左端點就要?于a,b的右端點的最?值，與所有區間按照左端點排序不符。
  綜上所述，所有區間按照按照「左端點」排序之后，「互相重疊的區間」都是「相鄰」的

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
double d;
struct node
{double l, r;
}a[N];bool cmp(node& x, node& y)
{return x.l < y.l;    
}int main()
{int cnt = 0;while (cin >> n >> d, n && d){cnt++;bool flg = false;for (int i = 1; i <= n; i++){double x, y; cin >> x >> y;if (y > d) flg = true;double l = sqrt(d * d - y * y);a[i].l = x - l, a[i].r = x + l;}cout << "Case " << cnt << ": ";if (flg) cout << -1 << endl;else{sort(a+1, a+n+1, cmp);int ret = 1;double r = a[1].r;for (int i = 2; i <= n; i++){double left = a[i].l, right = a[i].r;if (left <= r){r = min(r, right);}else{ret++;r = right;}}cout << ret << endl;}}return 0;
}

思考具體解法，從下?的情況中，篩選出沒有特別明顯的反例的組合：

1. 區間按照左端點從?到?+防曬霜從?到?（優先選?）；
2. 區間按照左端點從?到?+防曬霜從?到?（優先選?）；
3. 區間按照左端點從?到?+防曬霜從?到?（優先選?）；
4. 區間按照左端點從?到?+防曬霜從?到?（優先選?）；
5. 區間按照右端點從?到?+防曬霜從?到?（優先選?）；
6. 區間按照右端點從?到?+防曬霜從?到?（優先選?）。
7. 區間按照右端點從?到?+防曬霜從?到?（優先選?）；
8. 區間按照右端點從?到?+防曬霜從?到?（優先選?）。
   雖然看似很多，但是很容易在錯誤的策略中舉出「反例」。

• 區間按照左端點從小到大，優先選較小的點：
  

第一個區間選了a之后，b這個點就沒辦法分配了
實際上應該把a給第二個區間，b給第一個區間

• 區間按照左端點從小到大，優先選較大的點：
  

第一個區間選了b之后，a這個點就沒辦法分配了
實際上應該把b給第二個區間，a給第一個區間

• 區間按左端點從大到小，優先選較小的點：
  

第一個區間選了a之后，b這個點就沒辦法分配了
實際上應該把a給第二個區間，b給第一個區間

• 區間按左端點從大到小，優先選較大的點：
  

較小的點能夠更好地被后面的區間選擇

• 區間按右端點從小到大，優先選較小的點：
  較大的點能夠更好地被后面的區間選擇
• 區間按照右端點從小到大，優先選較大的點：
  

第一個區間選了b之后，a這個點就沒辦法分配了
實際上應該把b給第二個區間，a給第一個區間

• 區間按右端點從大到小，優先選較小的點：
  

把a給了第一個區間以后，b就沒辦法分配了
實際上應該把b給第一個區間，a給第二個區間

• 區間按右端點從大到小，優先選較大的點：
  

第一個區間選了b之后，a這個點就沒辦法分配了
實際上應該把b給第二個區間，a給第一個區間

綜上所述，有兩種組合沒有明顯的反例，分別是：

1. 區間按照「左端點從?到?」排序，防曬霜從?到?排序，「優先選擇較?」的防曬霜；
2. 區間按照「右端點從?到?」排序，防曬霜從?到?排序，「優先選擇較?」的防曬霜。
   實際上兩種情況都是正確的，我們取其?證明?下，另?種證明?式類似。

可以?「交換論證法」證明?式?的正確性：
從前往后依次?較「貪?解」和「最優解」針對每?個區間的決策，當找到第?個區間，它們的「分配決策不同」時：設貪?解?的是a防曬霜，最優解?的是b防曬霜，因為貪?解選的是最?的，所以有$a\le b$。
此時關于a 防曬霜的使?情況，可以分以下?種情況：

1. a防曬霜在「最優解中沒有使?」，那么我們可以直接?a防曬霜替換b防曬霜，此時最優解的「最優性」并沒有損失，那么貪?解就和最優解決策?致；
2. a防曬霜在「最優解的后續決策中使?了」，設b使?的區間是$[x_b,y_b]$，a使?的區間是$[x_a,y_a]$：
   易得：
   $$x_b\le b\le y_b,x_a\le a\le y_a$$
   因為我們是按照右端點從?到?排序的，所以$y_a\ge y_b$；
   綜上：
   $$x_a\le a\le b\le y_b\le y_a$$
   所以b也可以作?于「a作?的區間」，也就是在最優解中「a,b可以互換」，進?就轉換成貪?解。
   因此，針對每?個位置，我們都可以把最優解在「不失去其最優性的前提下」，轉化成「貪?解」

#include <bits/stdc++.h>
using namespace std;const int N = 2510;int n, m;
struct node
{int x;int y;
}a[N], b[N];bool cmp(node& x, node& y)
{return x.x > y.x;
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;for (int i = 1; i <= m; i++) cin >> b[i].x >> b[i].y;sort(a+1, a+1+n, cmp); //按左端點從大到小排序sort(b+1, b+1+m, cmp); //按陽光強度從大到小排序int ret = 0;for (int i = 1; i <= n; i++){int l = a[i].x, r = a[i].y;for (int j = 1; j <= m; j++){int w = b[j].x, &cnt = b[j].y;if (cnt == 0) continue;if (w < l) break;if (w > r) continue;ret++;cnt--;break;}}cout << ret << endl;return 0;
}

按照「起始時間」對所有奶?「從?到?」排序，然后「從前往后」依次安排每?頭奶?，設這頭奶?的產奶的時間區間是[a, b] ：

• 在已經有?的所有?棚?，如果「結束時間?于a」，就可以把這頭奶?放在這個?棚??；如果有很多符合要求的，可以隨便找?個。因為我們是按照起始時間從?到?排序，只要這些?棚都符合要求，對于后?的奶???也都符合要求。不妨找結束時間最早的，?便判斷。
• 如果所有已經有?的?棚的「結束時間都?于a 」，那么這頭?只能??單獨開?個?棚。
  這個貪?策略是?較符合我們「常識」的，盡量優的安排每?頭?

#include <bits/stdc++.h>
using namespace std;const int N = 5e4 + 10;int n;
struct node
{int x; //起始時間 / 結束時間int y; //終止時間 / 牛棚編號int z; //排序之前的編號bool operator<(const node& a) const{return x > a.x;}}a[N];int ret[N]; //存最終結果bool cmp(node& x, node& y)
{return x.x < y.x;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].x >> a[i].y;a[i].z = i;}sort(a+1, a+1+n, cmp);int num = 1;priority_queue<node> heap;ret[a[1].z] = 1;heap.push({a[1].y, 1});for (int i = 2; i <= n; i++){int l = a[i].x, r = a[i].y;if (l <= heap.top().x) //無法放在已經分配的牛棚里{num++;ret[a[i].z] = num;heap.push({r, num});}else{node t = heap.top(); heap.pop();ret[a[i].z] = t.y;heap.push({r, t.y});}}cout << num << endl;for (int i = 1; i <= n; i++) cout << ret[i] << endl;return 0;
}