회의실은 한 개만 존재한다 -> 여러 개의 스케줄 중 하나의 스케줄만 활성화가 된다. -> Activity Selection Problem
3. 문제 해결
회의가 끝나는 시간을 기준으로 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 기준으로 정렬한다.
정렬된 배열을 순차적으로 탐색하면서 시간이 겹치지 않는 회의를 찾아낸다.
4. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b)
{
return a.second != b.second ? a.second < b.second : a.first < b.first;
}
int solution(int N, vector<pair<int, int>>& meetings)
{
int answer = 0;
int lastEnd = 0;
// If the end times are different, sort the vector based on the end time
// if not, sort the vector based on the start time
sort(meetings.begin(), meetings.end(), compare);
// Count the number of meetings from the start time 0
for (int i = 0; i < N; i++)
{
if (meetings[i].first < lastEnd) continue;
answer++;
lastEnd = meetings[i].second;
}
return answer;
}
int main()
{
int N;
vector<pair<int, int>> meetings;
cin >> N;
for (int i = 0; i < N; i++)
{
int start, end;
cin >> start >> end;
meetings.push_back({ start, end });
}
cout << solution(N, meetings);
return 0;
}