leetcode

0 class Solution {

1 public:

2 int mostBooked(int n, vector<vector<int>> &meetings) const {

3 sort(begin(meetings), end(meetings));

4

5 typedef pair<long long, int> record;

6 priority_queue<record, vector<record>, greater<>> engaged;

7 priority_queue<int, vector<int>, greater<>> unused;

8 vector<int> count(n);

9

10 for (int i = 0; i < n; i++)

11 unused.push(i);

12

13 for (const auto meeting : meetings) {

14 const int s = meeting[0], e = meeting[1];

15

16 while (!engaged.empty() && engaged.top().first <= s) {

17 unused.push(engaged.top().second);

18 engaged.pop();

19 }

20

21 if (!unused.empty()) {

22 const int room = unused.top();

23 unused.pop();

24

25 count[room] += 1;

26 engaged.push({e, room});

27 } else {

28 const auto [end, room] = engaged.top();

29 engaged.pop();

30

31 count[room] += 1;

32 engaged.push({end + e - s, room});

33 }

34 }

35

36 int maxi = 0;

37 for (int i = 1; i < n; i++) {

38 if (count[i] > count[maxi]) maxi = i;

39 }

40

41 return maxi;

42 }

43 };