[Baekjoon] 1931 회의실배정

알고리즘 분류

그리디 알고리즘

문제 - https://www.acmicpc.net/problem/1931

-문제-

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

-해결방법-

처음에는 페이지에 나와있는 예제 처럼 오름차순으로 정렬되어 있는 줄 알고 그 부분을 신경쓰지 않아서 많이 틀렸습니다.ㅠㅠ이 문제의 핵심은 처음 입력값들을 오름차순으로 정렬 하고 조건에 맞게 문제를 푸는 것이 중요한 것 같습니다. -> sort()쓰는 법 알기!

<소스코드>

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; typedef struct time { int s, f; }T; bool compare(T &a, T &b) { if (a.f == b.f) return a.s < b.s; else return a.f < b.f; } #define MAX 100000 T conf_time[MAX]; int main(void) { int num, i; int count = 0; int greedy = 0; scanf("%d", &num); for (i = 0; i < num; i++) scanf("%d %d", &conf_time[i].s, &conf_time[i].f); sort(conf_time, conf_time + num, compare); count = 0; for (i = 0; i < num; i++) { if (greedy <= conf_time[i].s) { greedy = conf_time[i].f; count++; } } printf("%d\n", count); return 0; }