[BOJ/C++] 1931번 회의실 배정 : 그리디

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

문제해결

시작시간보다는 끝나는 시간을 확인해서 문제를 푸는게 핵심이다.

시작하는 시간과 끝나는 시간을 pair로 입력받고, 끝나는 시간을 오름차순으로 정렬한다.

만약 끝나는 시간이 똑같다면, 시작시간 오름차순으로 정렬한다.

이 후 회의 수 N개 만큼 for 문을 돌면서 t에 끝나는 시간을 넣고, 다음 시작시간보다 끝나는 시간이 더 클 경우

회의에 포함하지 않고 다음 인덱스로 넘긴다.

만약 if문 안에 들지 않을 경우 회의 수를 +1하고 끝나는 시간 뒤에 시작하는 회의 확인을 반복한다.

코드

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

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	else {
		return a.second < b.second;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	vector<pair<int, int>> vec;
	int N, S, E;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S >> E;
		vec.push_back(make_pair(S, E));
	}
	sort(vec.begin(), vec.end(), compare);
	int ans = 0;
	int t = 0;
	for (int i = 0; i < N; i++) {
		if (t > vec[i].first) continue;
		ans++;
		t = vec[i].second;
	}
	cout << ans;

}

using kotlin

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.math.*
import java.util.Vector

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    var time: MutableList<Pair<Int, Int>> = mutableListOf()
    for (i in 0 until N) {
        val input = readLine().split(" ")
        time.add(Pair(input[0].toInt(), input[1].toInt()))
    } // 각 time 다 넣기

    time = time.sortedWith(compareBy({ it.second }, { it.first })).toMutableList() //second 기준으로 오름차순,만약 second 동일 시 first 기준 오름차순

    var ans = 1
    var firstTime = time[0]
    for (i in 1 until N) {
        if (firstTime.second <= time[i].first) {
            firstTime = time[i]
            ans++
        }
    }
    println(ans)
}

그냥 sorted만 하면 리스트에 적용안되기 때문에 .toMutableList()로 만든 뒤 time에 재할당을 해줘야한다.
또한 second 기준으로 정렬한 뒤 second 동일 시 first 기준으로 정렬하는 compare를 설정해줘야 반례를 통과할 수 있다.