BOJ 1931 - 회의실 배정

문제

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

 

 

풀이

그리디 문제다

 

1. 회의가 끝나는 시간이 빠를수록 더 많은 회의를 고를 수 있다

2. 회의가 끝나는 시간 이후부터 가장 빨리 시작되는 회의를 골라야 한다

 

이를 위해 끝나는 시간이 작은 순서대로 오름차순 정렬을 한다

만약 끝나는 시간이 갔다면 시작 시간이 작은 순서대로 또 오름차순 정렬을 한다

 

 

코드

python

meet = []
answer = 0
endTime = 0
 
n = int(input())
 
for _ in range(n):
    begin, end = map(int, input().split())
    meet.append([begin, end])
 
meet.sort(key= lambda x: (x[1], x[0]))
 
for meet_begin, meet_end in meet:
    if endTime <= meet_begin:
        endTime = meet_end
        answer += 1
 
print(answer)
 

 

 

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int n;
    private static int[][] a;
 
    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
 
    private static void solve() {
        Arrays.sort(a, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
            }
        });
 
        int end = 0;
        int cnt = 0;
 
        for (int i = 0; i < n; i++) {
            if (a[i][0] >= end) {
                end = a[i][1];
                cnt++;
            }
        }
 
        System.out.println(cnt);
    }
 
    private static void input() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());
        a = new int[n][2];
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            a[i][0] = Integer.parseInt(st.nextToken());
            a[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
}
 

 

 

C++

#include <iostream>
#include <vector>
#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()
{
    int N;
    cin >> N;
 
    vector<pair<int, int>> v;
 
    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }
 
    sort(v.begin(), v.end(), compare);
 
    int count = 1;
    int end = v[0].second;
    for (int i = 1; i < N; i++)
    {
        if (v[i].first >= end)
        {
            end = v[i].second;
            count++;
        }
    }
 
    cout << count;
 
    return 0;
}