1931번: 회의실 배정

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

1931번: 회의실 배정

1. 문제 분석

회의 시간이 나오고 한 회의실로 최대 몇 개의 회의를 할 수 있는지 구하는 문제이다.

2. 코드 작성

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

pair<int, int> p_list[100000];

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()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int N, cnt = 1;
	cin >> N;
	for (int i = 0;i < N;i++)
	{
		cin >> p_list[i].first >> p_list[i].second;
	}
	sort(p_list, p_list + N, comp);
	int start = p_list[0].first, end = p_list[0].second;
	for (int i = 1;i < N;i++)
	{
		if (end > p_list[i].first)
		{
			continue;
		}
		else if (end <= p_list[i].first)
		{
			cnt++;
			end = p_list[i].second;
		}
	}
	cout << cnt;
	return 0;
}

3. 코드 분석

일단 끝나는 시각이 작은 순서대로 정렬을 했고 회의실을 사용하는 회의가 끝나는 시각을 end에 넣어줬고, i번째 항의 시작 시간을 end와 비교해줬다. end가 작으면 continue 크거나 같으면 cnt++해주고 end=i가 끝나는 시간 끝나는 시간은 같은데 시작 시간이 다른 것들은 if에서 걸러짐