題目描述
有n個點和m個區間，點和區間的端點全部是整數，對于點a和區間[b,c]，若a> =b且a< =c，稱點a滿足區間[b,c]。
求最小的點的子集，使得所有區間都被滿足。

數據規模和約定
1< =n,m< =10000
0< =點和區間的坐標< =50000
輸入
第一行兩個整數n m
以下n行 每行一個整數，代表點的坐標
以下m行 每行兩個整數，代表區間的范圍
輸出
輸出一行，最少的滿足所有區間的點數，如無解輸出-1。
樣例輸入
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
樣例輸出
2
這兩天做了幾道線段和點的貪心問題，很傷。。
總結起來，這種問題大概率要排序，按照左端點右端點都有可能，根據具體題意而定。
這道題目，我們先按照左端點升序排序，如果左端點相同，則按照右端點降序排序。這樣我們就能每次將點推到一個更遠的位置。而這樣做的次數，就是我們花費的點數。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e4+100; struct node{int s,e;bool operator<(const node &a)const{if(s!=a.s) return s<a.s;else return e>a.e;} }p[maxx]; int a[maxx]; int n,m;int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++) scanf("%d%d",&p[i].s,&p[i].e);sort(p+1,p+1+m);int k,i,j,st=1;for(k=0;k<n;k++)//操作的次數=最少需要的點數{int _max=1;for(i=1;i<=n;i++){for(j=st;j<=m;j++) if(p[j].s>a[i]||p[j].e<a[i]) break;if(j>_max) _max=j;//看這個點最多可以滿足多少個區間。}st=_max;//下次開始的時間就在上一次點的地方開始，尋找滿足的點if(st==m+1) break;//所有的線段滿足了，就直接退出。}if(k==n) cout<<"-1"<<endl;else cout<<k+1<<endl;return 0; }

努力加油a啊，(^o)/~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]线段和点（排序+贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。