(14464) 소가 길을 건너간 이유 4

https://www.acmicpc.net/problem/14464

단계별로 풀어보기

42단계(그리디 알고리즘 2) 4번째

 

 

 

소와 닭의 최대 연결 쌍을 찾는 문제. 이후 나올 이분 매칭이지만 A그룹의 가능한 B그룹 범위가 연속적이라는 특수한 경우다.

소의 시작 시간 Aj나 끝 시간 Bj만을 기준으로 정렬하면 정답이 나오지 않는다.

닭의 가능한 시간 Ti를 오름차순으로 정렬했을 때, 어떤 닭이 소를 도와줄 땐 가능한 소들 중 Bj가 가장 작은 소를 도와주는 것이 유리하다. 이후 남은 닭은 도와줄 수 있는 시간이 지금 닭보다 뒤쪽이기 때문이다.

이때 가능한 소의 범위는 Aj가 닭의 시간 Ti보다 작거나 같아야 하므로, 이 가능한 Aj를 전부 우선순위 큐에 넣고 우선순위 큐에서 Bj가 작은 순서, 같으면 Aj가 작은 순서대로 뽑아 비교하면 된다. 만약 Bj가 Ti보다 작다면 그 소는 지금 닭은 물론 이후의 닭도 도와줄 수 없으므로 버리고 다음 소를 뽑으면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> p;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int c, n;
  
  cin >> c >> n;
  
  vector<int> v(c);
  vector<p> w(n);
  
  auto cmp= [](p A, p B){
    if(A.second!=B.second)  return A.second>B.second;
    return A.first>B.first;
  };
  priority_queue<p, vector<p>, decltype(cmp)> pq(cmp);
  
  for(int i=0;i<c;i++)  cin >> v[i];
  for(int i=0;i<n;i++)  cin >> w[i].first >> w[i].second;
  
  sort(v.begin(), v.end());
  sort(w.begin(), w.end());
  
  int idx= 0, ans= 0;
  
  for(int x:v){
    while(idx<n && w[idx].first<=x){
      pq.push(w[idx]);
      idx++;
    }
    
    while(!pq.empty()){
      if(pq.top().first<=x && x<=pq.top().second){
        pq.pop();
        ans++;
        
        break;
      }
      
      pq.pop();
    }
  }
  
  cout << ans;
  
  return 0;
}