회의실 배정

문제

회의실 배정
유명한 웰노운 그리디 알고리즘 문제입니다.

풀이

먼저 회의를 시작 시간 기준으로, 시작 시간이 같으면 끝나는 시간을 기준으로 오름차순 정렬합니다. 정렬 기준으로 번째 회의의 시작 시간을 , 끝나는 시간을 라 합시다.

마지막으로 배치된 회의의 끝나는 시간을 라 합시다. 초기에 아무 회의도 배치되지 않았으므로 입니다. 부터 까지 탐색하여 이면 마지막으로 배치된 회의를 번째 회의로 대체합니다. 이렇게 하면 이미 배정된 회의는 건드리지 않으면서 회의가 일찍 끝나도록 할 수 있습니다.

가 되면 새로운 회의를 배정하고 같은 방식으로 답을 구하면 됩니다.

코드

Python

from dataclasses import dataclass
 
 
@dataclass
class Meeting:
    start: int
    end: int
 
 
n = int(input())
meetings = [Meeting(*map(int, input().split())) for _ in range(n)]
meetings.sort(key=lambda x: (x.start, x.end))
 
answer = 0
last_end = -1
for meeting in meetings:
    if last_end <= meeting.start:
        answer += 1
        last_end = meeting.end
    else:
        last_end = min(last_end, meeting.end)
 
print(answer)

C++

#include <bits/stdc++.h>
using namespace std;
 
struct Meeting {
    int start, end;
    auto operator<=>(const Meeting& m) const = default;
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<Meeting> meetings(n);
    for (auto& [start, end] : meetings)
        cin >> start >> end;
    ranges::sort(meetings);
 
    int answer = 0;
    int lastEnd = -1;
    for (auto [start, end] : meetings) {
        if (lastEnd <= start) {
            answer++;
            lastEnd = end;
        } else
            lastEnd = min(lastEnd, end);
    }
 
    cout << answer;
    
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        Meeting meetings[] = new Meeting[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(tk.nextToken()), end = Integer.parseInt(tk.nextToken());
            meetings[i] = new Meeting(start, end);
        }
 
        Arrays.sort(meetings);
 
        int answer = 0;
        int lastEnd = -1;
        for (Meeting m : meetings) {
            if (lastEnd <= m.start) {
                answer++;
                lastEnd = m.end;
            } else
                lastEnd = Math.min(lastEnd, m.end);
        }
 
        bw.write(answer + "");
        bw.close();
    }
}
 
class Meeting implements Comparable<Meeting> {
    int start, end;
 
    Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
 
    @Override
    public int compareTo(Meeting m) {
        if (start != m.start)
            return start - m.start;
        return end - m.end;
    }
}