백준[1931] 회의실 배정

해당 문제를 풀기 위해서

회의가 끝나는 시간들을 기준으로 오름차순 정렬을 한다.

가장 첫 번째 회의를 선택하여 계산을 진행하면 가장 많은 회의를 선택할 수 있다.

 

 

□ 소스코드

#include <bits/stdc++.h>

// 회의가 끝나는 시간을 기준으로 오름차순 정렬하는 함수
bool sorting(pair <int,int> p1, pair <int,int> p2) { // compare 함수
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    return p1.second < p2.second;
}

void meetingRoom(){
    int n;
    cin >> n;
    
    vector<pair<int,int>> v;
    
    // 입력받는 구문
    for(int i=0;i<n;i++){
        int start, end;
        cin >> start >> end;
        v.push_back(make_pair(start, end));
    }
    
    // 회의가 끝나는 시간을 기준으로 오름차순 정렬
    sort(v.begin(),v.end(),sorting);
    
    int count = 1;  // 회의가 가장 빨리 끝나는 것을 선택해서 값이 1부터 시작
    int finishMeet = v[0].second;   //회의가 가장 빨리 끝나는 것을 선택
    
    for(int i=1;i<n;i++){
        if( finishMeet <= v[i].first){  // 회의 끝나는 시간이 회의 시작 시간들 보다 작은 경우 해당 회의 실행
            finishMeet = v[i].second;   //회의 끝나는 시간 새롭게 저장
            count++;        //회의 횟수 증가
        }
        else{
            continue;
        }
        
    }
    
    cout<< count<<endl;
}

 

생각해보면 좋은 경우의 수

1. 회의 시작 시간이 같은 경우 
2. 코드에서 반복문을 돌릴 때 1부터 시작하는 이유

1번의 경우 앞에서 미리 회의가 먼저 끝나는 시간을 기준으로 오름차순 정렬을 완료한 상태이므로 상관이 없다.

2번의 경우 반복문을 돌릴 때 회의가 가장 먼저 끝나는 인덱스 0번째 값은 이미 선택했다고 생각한 상태라 인데스 1부터 시작한다.