백준 1931 - 회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예제 입력 1 복사

11

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8 12

2 13

12 14

예제 출력 1 복사

4

 

---

- 간단한 설명

회의의 시작시간과 종료시간을 입력받고 최대 몇번 회의를 진행할 수 있는지를 찾는다

 

 

 

 

 

- 문제풀이

2중 포문으로도 가능하나 시간초과가 발생하기 때문에 효율적인 방법을 찾아야한다

 

회의실을 최대로 사용하기 위해선 끝나는시간이 짧아야한다

 

각 회의의 시작, 종료 시간을 입력받고, 종료시간을 기준으로 오름차순으로 정렬한다. 종료시간이 같을 경우엔 시작시간을 기준으로 오름차순 정렬을 시킨다

 

예제에서 입력하는 데이터가 이미 종료시간을 기준으로 오름차순 정렬되어있는 데이터이다

 

1 4

3 5

0 6

5 7

3 8

5 9

6 10

8 11

8 12

2 13

12 14

 

4분에 끝나게 되면 시작시간이 4분보다 크거나 같은 회의를 찾는다

 

다음 회의는 5분에 시작하는 회의이다. 이 회의는 7분에 끝나므로 7분보다 크거나 같은 회의를 찾는다

 

다음 회의는 8분에 시작하는 회의이다. 이 회의는 11분에 끝나므로 11분보다 크거나 같은 회의를 찾는다

 

다음 회의는 12분이고 더이상 찾을 수 없으므로 종료한다

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool comp(pair<int,int> &a, pair<int,int> &b){
	if(a.second==b.second){
		return a.first<b.first;
	}
	return a.second<b.second;
}

int main(){
	vector<pair<int, int> >  vec;
	int N, val=1, start;
	scanf("%d", &N);
	vec.resize(N);
	for(int i=0; i<N; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		vec[i]={a,b};
	}
	
	sort(vec.begin(), vec.end(), comp);
	int s=vec[0].second;
		
	for(int i=1; i<N; i++){
		if(vec[i].first>=s){
			s=vec[i].second;
			val++;
		}
	}
    
	printf("%d", val);
	return 0;
}