[BOJ][1931] 회의실 배정

1. 문제 링크

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

2. 사용 알고리즘

그리디

3. 풀이

회의가 끝나는 시간순으로 오름차순 정렬(끝나는 시간이 같은 경우 시작시간 기준 오름차순) 후 일찍 끝나는 회의부터 하나씩 배정

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1931.cpp

#include <iostream>
#include <algorithm>

using namespace std;

struct Meeting {
    int begin;
    int end;
};

Meeting arr[100003];

bool cmp(const Meeting &u, const Meeting &v) {
    if(u.end == v.end) {
        return u.begin < v.begin;
    }
    return u.end < v.end;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> arr[i].begin >> arr[i].end;
    sort(arr, arr + n, cmp);
    int ans = 0;
    int temp = 0;
    for(int i = 0; i < n; ++i) {
        if(temp <= arr[i].begin) {
            temp = arr[i].end;
            ++ans;
        }
    }
    cout << ans << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1931.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static class Meeting implements Comparable<Meeting> {
        int begin, end;

        Meeting(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }

        @Override
        public int compareTo(Meeting o) {
            if(this.end == o.end) return Integer.compare(this.begin, o.end);
            return Integer.compare(this.end, o.end);
        }
    }

    static List<Meeting> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            int b = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list.add(new Meeting(b, e));
        }
        Collections.sort(list);
        int ans = 0;
        int temp = 0;
        for(int i = 0; i < n; ++i) {
            if(temp <= list.get(i).begin) {
                temp = list.get(i).end;
                ++ans;
            }
        }
        System.out.println(ans);
    }
}