[코딩테스트C++]회의실배정

오늘의 문제

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

회의실배정

나의 풀이

// 회의실배정
int solution(vector<vector<int>> a){
    int answer =1;
    
    sort(a.begin(), a.end(), cmp);
    int end = a[0][1];
    for(int i=1;i<a.size();i++){
        if(a[i][0] >= end){
            answer++;
            end = a[i][1];
        }else{
            if(a[i][1]< end){
                end = a[i][1];
            }
        }
    }
    return answer;
}

풀이 법

• 일단 회의실 이용시간이 unsorted되어있어서 sort를 수행했다
• 그 다음에 회의실 사용횟수를 최대로 하기 위해 시작이 종료보다 앞설 경우 종료가 빠른 시간으로 갱신했음
• 시작이 종료보다 크거나 같은 경우는 회의실 사용횟수를 증가시키며 end를 갱신했음
• 왜 그럴 수 있었냐면 sort되어있기 때문에 그보다 더 빠르게 종료하고 일찍 시작하는 시간은 없기 때문

모범 답안

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N; cin >> N;

	pair<int, int> schedule[100000];
	for (int i = 0; i < N; ++i) {
		cin >> schedule[i].second >> schedule[i].first;
	}
	sort(schedule, schedule + N);
	int cnt = 0;
	int t = 0;
	for (int i = 0; i < N; ++i) {
		if (t > schedule[i].second) continue;
		cnt++;
		t = schedule[i].first;
	}
	cout << cnt;
	return 0;
}

배울 점

• 종료가 더 작을 수 없으므로 조건에 포함된다. 한번더 생각해보면 연산을 줄일 수 있다.