BOJ 1931 c++

알고리즘

BOJ 1931 회의실배정 c++

백준 1931

#include <bits/stdc++.h>
using namespace std;

# define X first
# define Y second

int n;
pair<int, int> s[100002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    // 정렬의 편의를 위해 끝 시각, 시작 시각으로 받음.
    for (int i = 0; i < n; i++)
        cin >> s[i].Y >> s[i].X; 
    sort(s, s + n);
    int count = 0;
    int currentTime = 0;
    for (int i = 0; i < n; i++) {
        // 맨 처음에는 s[0]에 가장 끝나는 시간이 빠른 회의가 담김.
        if (currentTime > s[i].Y)
            continue;
        currentTime = s[i].X;
        count++;
    }
    cout << count;
    return 0;
}

그리디 알고리즘을 이용.
참명제는 먼저 끝나는 회의를 기준으로 회의공간을 예약하면 가장 많이 예약할 수 있다는 것.

max_element는 시작주소와 마지막주소 + 1을 넣으면 최대값이 담긴 곳의 주소를 리턴하는 함수.