题目描述
There are N islands lining up from west to east, connected by N−1 bridges.
The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.
One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:
Request i: A dispute took place between the ai-th island from the west and the bi-th island from the west. Please make traveling between these islands with bridges impossible.
You decided to remove some bridges to meet all these M requests.
Find the minimum number of bridges that must be removed.
Constraints
·All values in input are integers.
·2≤N≤105
·1≤M≤105
·1≤ai<bi≤N
·All pairs (ai,bi) are distinct.
输入
Input is given from Standard Input in the following format: N M a1 b1 a2 b2 : aM bM
输出
Print the minimum number of bridges that must be removed.
样例输入
5 2 1 4 2 5
样例输出
1
提示
The requests can be met by removing the bridge connecting the second and third islands from the west.
#include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 struct node { int l; int r; }; node a[100500]= {0}; bool cmp(node a,node b) { if(a.l!=b.l) return a.l<b.l; else return a.r<b.r; } ll sum=1; int main() { int n=read,m=read; for(int i=0;i<m;i++) a[i].l=read,a[i].r=read; sort(a,a+m,cmp); int minn=a[0].r; for(int i=1;i<m;i++) { if(a[i].l>=minn) { sum++; minn=a[i].r; } else minn=min(a[i].r,minn); } printf("%lld\n",sum); return 0; } /************************************************************** Language: C++ Result: 正确 Time:56 ms Memory:2812 kb ****************************************************************/