-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path#21.cpp
More file actions
46 lines (37 loc) · 1010 Bytes
/
#21.cpp
File metadata and controls
46 lines (37 loc) · 1010 Bytes
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int roomsNeeded(vector<pair<int, int>> ×){
// Make list of all events and their corresponding times
vector<pair<int, int>> events;
for (pair<int, int> p : times) {
events.push_back(make_pair(p.first, 1)); // start event
events.push_back(make_pair(p.second, -1)); // end event
}
// sort the events in order based on time
sort(events.begin(), events.end());
int roomsUsed = 0;
int maxRooms = 0;
for (pair<int, int> p : events) {
// increments or decrements depending on whether event is start or end
roomsUsed += p.second;
maxRooms = max(roomsUsed, maxRooms);
}
return maxRooms;
}
int main() {
string in;
cin >> in;
int n = stoi(in);
vector<pair<int, int>> times;
for (int i = 0; i < n; i++) {
cin >> in;
int start = stoi(in);
cin >> in;
int end = stoi(in);
times.push_back(make_pair(start, end));
}
cout << "Classrooms Needed: " << roomsNeeded(times) << endl;
}