演算法

1class MinHeap {
2  private a: number[] = [];
3  get size() { return this.a.length; }
4  peek() { return this.a[0]; }
5  push(x: number) {
6    const a = this.a;
7    a.push(x);
8    for (let i = a.length - 1; i > 0; ) {
9      const p = (i - 1) >> 1;
10      if (a[p] <= a[i]) break;
11      [a[p], a[i]] = [a[i], a[p]];
12      i = p;
13    }
14  }
15  pop() {
16    const a = this.a, top = a[0], last = a.pop()!;
17    if (a.length) {
18      a[0] = last;
19      for (let i = 0; ; ) {
20        const l = 2 * i + 1, r = l + 1;
21        let m = i;
22        if (l < a.length && a[l] < a[m]) m = l;
23        if (r < a.length && a[r] < a[m]) m = r;
24        if (m === i) break;
25        [a[m], a[i]] = [a[i], a[m]];
26        i = m;
27      }
28    }
29    return top;
30  }
31}
32 
33function minRoomsBrute(meetings: [number, number][]): number {
34  let best = 0;
35  for (const [start] of meetings) {
36    let busy = 0;
37    for (const [s, e] of meetings) {
38      if (s <= start && start < e) busy++;
39    }
40    best = Math.max(best, busy);
41  }
42  return best;
43}
44 
45function minRoomsHeap(meetings: [number, number][]): number {
46  const sorted = [...meetings].sort((a, b) => a[0] - b[0]);
47  const ends = new MinHeap();
48  let best = 0;
49  for (const [start, end] of sorted) {
50    if (ends.size && ends.peek() <= start) ends.pop();
51    ends.push(end);
52    best = Math.max(best, ends.size);
53  }
54  return best;
55}
56 
57function minRoomsSweep(meetings: [number, number][]): number {
58  const starts = meetings.map((m) => m[0]).sort((a, b) => a - b);
59  const ends = meetings.map((m) => m[1]).sort((a, b) => a - b);
60  let rooms = 0, best = 0, j = 0;
61  for (const start of starts) {
62    while (j < ends.length && ends[j] <= start) {
63      rooms--;
64      j++;
65    }
66    rooms++;
67    best = Math.max(best, rooms);
68  }
69  return best;
70}