글 읽기 - 반례 부탁드립니다

p_ce1052 3년 전 0

이분매칭이나 에드몬드 카프는 시간초과가 날 것 같아서 그리디하게 풀었습니다.

시작 책 번호가 가장 빠른 순으로 먼저 정렬하여 현재 (a1,a2)를 보고있고 다음 구간이 (b1,b2)라 할 때

a2가 b2보다 작거나 같다면 항상 a부터 매칭시켜주는게 이득이고

a2가 b2보다 크다면 a1~b1이전까지의 책이 비어있다면 거기에 a를 매칭시키고 비어있지 않다면 b를 먼저 매칭시켜보고 a를 나중에 매칭시키기 위해 a를 (b1,a2)로 잘라서 다시 pq에 넣었습니다. 어디가 잘못되었는지 모르겠습니다

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
int solve(){
	int n,m;	
	cin>>n>>m;
	priority_queue<pi,vector<pi>,greater<pi> >pq;
	while(m--){
		ll a,b;
		cin>>a>>b;
		pq.push(pi(a,b));
	}
	bool used[1005] = {false};
	int ans = 0;
	while(pq.size()){
		int l = pq.top().first;
		int r = pq.top().second;
		pq.pop();
		if(pq.empty()){ //마지막 구간이라면 그냥 그리디하게 매칭
			for(int i = l; i<=r; i++){
				if(!used[i]){
					ans++;
					break;
				}
			}
		}
		else{
			if(pq.top().second>=r){ //다음 구간의 끝보다 현재 구간의 끝이 작다면
				for(int i=l; i<=r; i++){ //나부터 매칭시키는게 이득
					if(!used[i]){
						used[i] = true;
						ans++;
						break;
					}
				}
			}
			else{ //내가 더 크다면 겹치지 않는 부분에 매칭시킬 수 있는지 확인하고 
				bool pos = false;
				for(int i=l; i<pq.top().first; i++){
					if(!used[i]){
						pos = true;
						ans++;
						used[i] = true;
						break;
					}
				}
				if(pos) continue;
				else{ //매칭시킬 수 없다면 나중에 매칭시킨다. 
					pq.push(pi(pq.top().first,r));
				}
			}
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		cout<<solve()<<'\n';
	}
}