(C++) baekjoon 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

 

---

<code>

/*
2022_10_17
backjoon 1931 coin https://www.acmicpc.net/problem/1931
*/
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){

    int n; // n = 회의의 수
    int start, end; //start = 회의시작시간 end = 회의종료시간
    cin >> n;
   
    vector<pair<int,int>> time; // 회의 타임 pair vector로 입력

    for(int i = 0; i < n; i++){
        cin >> start >> end;
        time.push_back(make_pair(end, start));
    }
    sort(time.begin(), time.end());

    int temp = time[0].first; //가장빠른 end time
    int count = 1;
    for (int i = 1 ;i < n; i++){
		if (temp <= time[i].second) //end time과 다음 스케줄 start타임
		{
			count++;
			temp = time[i].first;
		}
	}
    cout << count;

    return 0;
}

---

이번문제는 생각도 많이 했어야 했고 고민도 많이 했던 문제이다.

가장먼저 이번문제를 풀면서 pair arrary라는것을 알게되었다.(https://han-kjin.tistory.com/m/entry/C-pair-array)

(C++) pair array

문제는 회의의 수를 입력받고 각 회의가 시작하는시간과 끝나는 시간을 입력받아 최대 몇개의 회의를 진행시킬 수 있는가에 대한 문제였는데 (이때 하나의 회의가 끝나는 시간과 다른 회의가 시작하는 시간이 같은경우 끝나자 마자 시작하는 경우로 침 ex) [1 2], [2 3] <- 2개의 회의 진행 가능) 시작과 끝 시간을 하나의 배열에 정리하기 위해 vector pair 를 사용하였고, 각 시작시간과 끝나는시간을 정렬(sort)해 주었다.

다음부분이 많이 헷갈렸는데 시작시간이 아무리 빠르더라도 늦게 끝나면 최대의 회의를 구할 수 없기 때문에 temp변수에 초기값으로  가장 빠른타임에 끝나는 회의를 넣어주었다. 다음으로는 temp와 다음 타임의 회의 시작시간을 비교하여 temp보다 크거나, 같은 회의 시작시간을 찾아주었고, 찾은경우 count변수를 1더해주어 회의의 갯수를 카운트 하였다.

비교한 다음으로 temp에는 앞서 구한 temp보다 크거나 같은 회의타임의 끝나는 시간(end)을 넣어 주어 모든 회의시간을 비교할 때 까지 반복하여 비교하며 총 회의 시간을 구하였다.