POJ(PKU) 3190 Stall Reservations

解法：貪欲
こめんと：priority_queueはとても便利。

#include <cstdio>
#include <utility>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;

int main(){
  
  int out[50002]={0};
  
  int n;
  int ans = 0;
  
  priority_queue<PP ,vector<PP>,greater<PP> > que;
  
  scanf("%d",&n);
  
  for(int i = 0;i < n;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    que.push(PP(a,P(b,i)));
  }
  
  priority_queue<P ,vector<P>,greater<P> > q;
  
  while(que.size()){
    PP tmp = que.top(); que.pop();
    
    int fir = tmp.first;
    int sec = tmp.second.first;
    int ban = tmp.second.second;
    
    
    
    if(q.empty() || q.top().first >= fir){
      ans++;
      out[ban] = ans;
      q.push(P(sec,ans));
    }else{
      out[ban] = q.top().second;
      q.pop();
      q.push(P(sec,out[ban]));
    }
  }
  
  printf("%d\n",ans);
  
  for(int i = 0;i < n;i++){
    printf("%d\n",out[i]);
  }
  
  return 0;
}