https://www.acmicpc.net/problem/1931
그리디 알고리즘
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다. |
code>>
#include <iostream>
#include <algorithm>
#include <vector>
std::pair<long long, long long> input[100001];
long long time[100001];
bool Compare(const std::pair<long long, long long>& left, const std::pair<long long, long long>& right)
{
if (left.first == right.first)
return left.second < right.second;
else
return left.first < right.first;
}
int main()
{
std::ios::ios_base::sync_with_stdio(false);
int N;
std::cin >> N;
for (int i = 0; i < N; i++)
{
std::pair<long long, long long> p;
std::cin >> p.first >> p.second;
input[i] = p;
}
std::sort(input, input + N, Compare);
auto count = 1;
auto sel = input[0];
for (int i = 1; i < N; i++)
{
if (input[i].first >= sel.second)
{
count++;
sel = input[i];
}
else if(input[i].second <sel.second)
sel = input[i];
}
printf("%d\n", count);
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
| 2448>별 찍기 - 11 (0) | 2018.11.12 |
|---|---|
| 4367>셀프 넘버 (0) | 2018.10.21 |
| 3665>최종순위 (0) | 2018.10.20 |
| 2252>줄 세우기 (0) | 2018.10.15 |
| 9095>1,2,3 더하기 (0) | 2018.10.15 |