aboutsummaryrefslogtreecommitdiff
path: root/meeting_rooms3.c
diff options
context:
space:
mode:
Diffstat (limited to 'meeting_rooms3.c')
-rw-r--r--meeting_rooms3.c109
1 files changed, 109 insertions, 0 deletions
diff --git a/meeting_rooms3.c b/meeting_rooms3.c
new file mode 100644
index 0000000..462d84e
--- /dev/null
+++ b/meeting_rooms3.c
@@ -0,0 +1,109 @@
+// 2402. Meeting Rooms III
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n', there are 'n' rooms numbered 0 to 'n - 1'.
+ * guven a 2d integer array 'meetings', where 'meetings[i] = start[i], end[i]'
+ * means that a meeting will be held during the half closed time interval
+ * '[start[i], end[i]]'. all thevalues of 'start[i]' are unique. meetings are
+ * allocated to rooms in the following manner: each meeting will take place in
+ * the unused room with the lowest number. if there are no available rooms, the
+ * meeting will be delayed until a room becoms free. the dleayed meeting should
+ * have the same duration as the original meeting. when a room becoms unused,
+ * meetings that have an earlier original start time should be given the room,
+ * return the number of the room that held the most meetings. if there are
+ * multiple rooms, return the room with the lowest number. a half closed
+ * interval '[a, b)' is the interval between 'a' and 'b' including 'a' and not
+ * including 'b'.
+ */
+
+void heapdown(int **room, int *heap, int heapsize) {
+ int curr = 1;
+ int child = curr << 1;
+ while (child <= heapsize) {
+ if (child + 1 <= heapsize &&
+ room[heap[child + 1]][0] < room[heap[child]][0])
+ child++;
+ if (room[heap[child]][0] >= room[heap[curr]][0])
+ break;
+ heap[curr] ^= heap[child];
+ heap[child] ^= heap[curr];
+ heap[curr] ^= heap[child];
+ curr = child;
+ child <<= 1;
+ }
+}
+void heapup(int **room, int *heap, int heapidx, int roomidx) {
+ int curr = heapidx;
+ int father = curr >> 1;
+ while (father >= 1) {
+ if (room[heap[father]][0] <= room[roomidx][0])
+ break;
+ heap[curr] = heap[father];
+ curr = father;
+ father >>= 1;
+ }
+ heap[curr] = roomidx;
+}
+int cmp(const void *a, const void *b) {
+ return (*(int **)a)[0] - (*(int **)b)[0];
+}
+int mostBooked(int n, int **meetings, int meetingsSize, int *meetingsColSize) {
+ long long **room = malloc(n * sizeof(long long *));
+ for (int i = 0; i < n; i++) {
+ room[i] = malloc(4 * sizeof(long long));
+ room[i][0] = i;
+ room[i][1] = i;
+ room[i][2] = -1;
+ room[i][3] = 0;
+ }
+ qsort(meetings, meetingsSize, sizeof(meetings[0]), cmp);
+ int *nonbook = malloc((n + 1) * sizeof(int));
+ int *booked = malloc((n + 1) * sizeof(int));
+ int nonbookidx = 0; // 1~n
+ int bookidx = 0; // 1~n
+ for (int i = 0; i < n; i++) {
+ heapup(room, nonbook, i + 1, nonbookidx++);
+ }
+ for (int i = 0; i < meetingsSize; i++) {
+ long long poptime = meetings[i][0];
+ int target = 0;
+ if (nonbookidx == 0)
+ poptime = fmax(poptime, room[booked[1]][0]);
+ // booked ->nonbooked
+ while (bookidx > 0 && room[booked[1]][0] <= poptime) {
+ target = booked[1];
+ room[target][0] = room[target][1];
+ heapup(room, nonbook, ++nonbookidx, target);
+ booked[1] = booked[bookidx--];
+ heapdown(room, booked, bookidx);
+ }
+ // nonbooked ->booked
+ target = nonbook[1];
+ room[target][2] = (room[target][2] <= meetings[i][0])
+ ? meetings[i][1]
+ : room[target][2] + meetings[i][1] - meetings[i][0];
+ room[target][3] += 1;
+ room[target][0] = room[target][2];
+ heapup(room, booked, ++bookidx, target);
+ nonbook[1] = nonbook[nonbookidx--];
+ heapdown(room, nonbook, nonbookidx);
+ }
+ int ans = 0;
+ int count = -1;
+ for (int i = 0; i < n; i++) {
+ if (room[i][3] > count) {
+ count = room[i][3];
+ ans = i;
+ }
+ }
+
+ return ans;
+}
+
+int main() {
+ int m1[5][2] = {{0, 10}, {1, 5}, {2, 7}, {3, 4}},
+ m2[5][2] = {{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}}, *mcs1, *mcs2;
+ printf("%d\n", mostBooked(2, (int **)m1, 5, mcs1)); // expect: 0
+ printf("%d\n", mostBooked(3, (int **)m2, 5, mcs2)); // expect: 1
+}