This repository was archived by the owner on Sep 30, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlab12.cpp
More file actions
85 lines (61 loc) · 1.84 KB
/
lab12.cpp
File metadata and controls
85 lines (61 loc) · 1.84 KB
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "lab.h"
class Lecture {
public:
int start = 0;
int end = 0;
};
int min_num_lecture_halls(std::vector<Lecture>& le) {
if (le.size() == 0) return 0;
auto compare = [](Lecture& l1, Lecture& l2) {
return l1.start < l2.start;
};
std::sort(le.begin(), le.end(), compare);
std::vector<int> halls;
// 至少有一间报告厅
halls.push_back(le[0].end);
int idx;
for (int i = 1; i < le.size(); i++) {
// 找到最早结束的讲座
auto end = std::min_element(halls.begin(), halls.end());
if (le[i].start >= *end) {
// 如果能开讲座就将结束时间更新
idx = std::distance(halls.begin(), end);
halls[idx] = le[i].end;
}
else {
// 不能开讲座就多加一间报告厅
halls.push_back(le[i].end);
}
}
return halls.size();
}
// 使用优先队列优化
int min_num_lecture_halls_priority_queue(std::vector<Lecture>& le) {
if (le.size() == 0) return 0;
auto compare = [](Lecture& l1, Lecture& l2) {
return l1.start < l2.start;
};
std::sort(le.begin(), le.end(), compare);
// 小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> halls;
// 至少有一间报告厅
halls.push(le[0].end);
for (int i = 1; i < le.size(); i++) {
if (le[i].start >= halls.top()) {
// 如果能开讲座则弹出一个报告厅
halls.pop();
}
// 无论如何都加一间报告厅
halls.push(le[i].end);
}
return halls.size();
}
void lab12() {
int n;
std::cin >> n;
std::vector<Lecture> lectures(n);
for (int i = 0; i < lectures.size(); i++) {
std::cin >> lectures[i].start >> lectures[i].end;
}
std::cout << min_num_lecture_halls(lectures);
}