aboutsummaryrefslogtreecommitdiff
path: root/meeting_rooms3.c
blob: 462d84e4c01f2c6a70d819ea422da1e54d27d9b5 (plain)
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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
}