TLE挂0求调

常规
1

忙碌的老师

image
image

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b){
  if(a.f==b.f)return a.s<b.s;
  return a.f<b.f;
}int main(){
  int n,m,p,last,ans=0;
  pair<int,int>a[100001];
  set<int>st;
  cin>>n;m=n;
  for(int i=0;i<n;i++){
    cin>>a[i].f>>a[i].s;
    st.insert(i);
  }sort(a,a+n,cmp);
  while(m){
    last=a[*st.begin()].s;
    for(auto i=*st.begin();i!=*st.end();){
      if(a[i].f>last)continue;
      m--;
      last=a[i].s;
      i++;
      st.erase(i-1);
    }ans++;
  }cout<<ans;
  return 0;
}
2 个赞
2

现在70分TLE

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b){
  if(a.f==b.f)return a.s<b.s;
  return a.f<b.f;
}int main(){
  int n,p=0;
  bool e;
  pair<int,int>a[100001];
  priority_queue<int>b[100001];
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i].f>>a[i].s;
  sort(a,a+n,cmp);
  b[p++].push(a[0].s);
  for(int i=1;i<n;i++){
    e=1;
    for(int j=0;j<p;j++){
      if(b[j].top()<a[i].f){
        b[j].push(a[i].s);
        e=0;
        break;
      }
    }if(e)b[p++].push(a[i].s);
  }cout<<p;
  return 0;
}
1 个赞