글 읽기 - 강의가 끝나는 시간으로 정렬하면 틀리는 이유가 무엇일까요..?

sihyun93 7년 전 4

min heap을 이용하여 문제를 해결하였습니다.

그런데 처음에는 강의를 끝나는 시간을 기준으로 오름차순으로 정렬하였으나

계속 틀려 강의 시작 시간을 기준으로 오름차순으로 정렬하였더니 정답이네용...

아무리 생각해도 잘 모르겠는데 반례를 들어주실 분 있으신가요?

코드 첨부 하겠습니다

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
typedef struct{
	int s; // 시작시간
	int t; // 끝시간
}time;
bool Compare(const time& x,const time& y){
	if(x.t == y.t)
		return x.s < y.s;
	return x.t < y.t;
	
}
int main(){
	int n;
	priority_queue<int,vector<int>,greater<int> > pq;

	time t;
	vector<time> v;
	scanf("%d",&n);
	for(int i = 0 ; i < n ; i++){
		scanf("%d %d",&t.s,&t.t);
		v.push_back(t);
	}
	sort(v.begin(),v.end(),Compare);

	pq.push(v[0].t);
	for(int i = 1 ; i < n ; i++){
		if(pq.top()>v[i].s){
			pq.push(v[i].t);
		}
		else{
			pq.pop();
			pq.push(v[i].t);
			}	
		}
	printf("%d\n",pq.size());
	return 0;
}

gloomy_sunday 6년 전 8

6
1 3
2 5
7 8
4 12
9 10
7 11

anacoluthon 5년 전 6

저도 고민했던터라, 다른 분들을 위해 남겨봅니다.

1 2

1 4

2 6

4 5

같은 경우입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

강의가 끝나는 시간으로 정렬하면 틀리는 이유가 무엇일까요..?

sihyun93 7년 전 4

gloomy_sunday 6년 전 8

anacoluthon 5년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말