$10^6$的数据捏
$O(n^2)$的复杂度跑不过去的,要用$O(n\log{n})$的快排捏
by SuperChao @ 2023-10-17 20:44:36
@[SuperChao](/user/916130)
```
#include<stdio.h>
#define N 1000005
struct time{//定义结构体
int x;
int y;
};
int n;
struct time t[N];
struct time temp;
long long sum=1;
void quick(struct time a[],int low,int high){
int i=low;
int j=high;
if(i>=j) return;
int tt=a[low].y;
if(i!=j){
while(a[j].y>=tt&&i<j){
j--;
}
while(a[i].y<=tt&&i<j){
i++;
}
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i];
a[i]=a[low];
a[low]=temp;
quick(a,low,i-1);
quick(a,i+1,high);
}
int main(){
scanf("%d",&n);//输入
for(int i=1;i<=n;i++){
scanf("%d%d",&t[i].x,&t[i].y);
}
quick(t,1,n);
int min=t[1].y;
for(int i=1;i<=n;i++){//判断
if(t[i].x>=min){
sum++;
min=t[i].y;
}
}
printf("%lld",sum);
return 0;
}
```
我改了快排后34567WA
8910TLE 可以帮忙看一下哪里有问题吗。我看不出来,万分感谢。已关。
by ZM_123_ @ 2023-10-18 20:20:04
可以不用快排,用sort也可以。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct sturct{
int start, end;
}a[N];
bool cmp(sturct a, sturct b){
return a.end<b.end;
}
int main(){
int n;
cin >> n;
for(int i=1; i<=n; i++){
cin >> a[i].start >> a[i].end;
}
sort(a+1, a+1+n, cmp);
int time=0, ans=0;
for(int i=1; i<=n; i++){
if(a[i].start>=time){
ans++;
time=a[i].end;
}
}
cout << ans;
return 0;
}
```
@[ZM_123_](https://www.luogu.com.cn/user/867752)
by Super_Ken @ 2023-11-30 17:53:04