💡 그리디 알고리즘/정렬
Memory 2776KB Time 1772ms Code Length 775B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct info{
int start;
int end;
};
bool compare(info &first, info &second) {
if (first.end < second.end) return true;
else if (first.end == second.end) {
if (first.start < second.start) return true;
}
return false;
}
int main()
{
int tc;
scanf("%d", &tc);
vector<info> v;
for (int i = 0; i < tc; i++) {
info tmp;
scanf("%d %d", &tmp.start, &tmp.end);
getchar();
v.push_back(tmp);
}
sort(v.begin(), v.end(), compare);
int cnt = 0;
info tmp = v.front(); v.erase(v.begin());
int last_time = tmp.end;
cnt++;
while (!v.empty()) {
info tmp = v.front(); v.erase(v.begin());
if (tmp.start < last_time) continue;
last_time = tmp.end;
cnt++;
}
printf("%d\n", cnt);
}
이 코드는 구조체 info를 정의하고, info의 start와 end 값을 가지고 있는 벡터를 생성한다. 그리고 compare 함수를 정의하여 end 값으로 정렬하되, end 값이 같을 경우 start 값으로 오름차순 정렬한다.
main 함수에서는 테스트 케이스의 개수를 입력받고, 각 테스트 케이스의 start와 end 값을 입력받아 벡터에 저장한다. 그 후, 벡터를 compare 함수를 사용하여 정렬한다.
그 다음, 첫 번째 요소를 꺼내서 last_time에 저장하고 cnt를 1 증가시킨다. 벡터가 비어있지 않은 동안, 벡터의 첫 번째 요소를 꺼내서 해당 요소의 start 값이 last_time보다 작다면 continue를 하고, 그렇지 않으면 last_time을 해당 요소의 end 값으로 업데이트하고 cnt를 1 증가시킨다.
마지막으로, cnt 값을 출력한다.
