[백준] 1931번: 회의실 배정 - java, C++

문제

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

 

접근법

문제에서 출력하고자 하는 것이 애매하게 써있다.. 한 개의 회의실에서 진행할 수 있는 회의의 갯수를 출력하는 문제이다. 단순하게 생각하면 가장 빨리 끝나는 회의 순으로 진행하면 된다. 현재 회의가 회의실을 사용할 수 없는 경우만 체크해주면 된다.

 

풀이

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static Meeting[] meetings;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        meetings = new Meeting[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(meetings);

        int current = 0;
        int answer = 1;
        for (int i = 1; i < N; i++) {
            if (meetings[i].start >= meetings[current].end) {
                answer++;
                current = i;
            }
        }

        System.out.println(answer);
    }

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

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

        @Override
        public int compareTo(Meeting meeting) {
            if (this.end == meeting.end) {
                return this.start - meeting.start;
            }
            return this.end - meeting.end;
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<pair<int, int>> meeting;

bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) {
        return a.first < b.first;
    }

    return a.second < b.second;
}

int main() {
    cin >> N;
    for (auto i = 0; i < N; i++) {
        int s, e;
        cin >> s >> e;
        meeting.push_back(make_pair(s, e));
    }

    sort(meeting.begin(), meeting.end(), compare);

    int answer = 1;
    int end = meeting[0].second;
    for (auto i = 1; i < N; i++) {
        if (end <= meeting[i].first) {
            end = meeting[i].second;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

 

전형적인 그리디 문제다!