Meeting Rooms III

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue<int, vector<int>, greater<int>> freeRooms;
        for (int i = 0; i < n; ++i) freeRooms.push(i);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> busy;
        vector<int> count(n, 0);
        for (auto& m : meetings) {
            long long s = m[0], e = m[1];
            while (!busy.empty() && busy.top().first <= s) {
                freeRooms.push(busy.top().second);
                busy.pop();
            }
            if (!freeRooms.empty()) {
                int r = freeRooms.top(); freeRooms.pop();
                busy.push({e, r});
                ++count[r];
            } else {
                auto [end, r] = busy.top(); busy.pop();
                busy.push({end + (e - s), r});
                ++count[r];
            }
        }
        int best = 0;
        for (int i = 1; i < n; ++i) if (count[i] > count[best]) best = i;
        return best;
    }
};

import (
    "container/heap"
    "sort"
)

type intHeap []int

func (h intHeap) Len() int            { return len(h) }
func (h intHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h intHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *intHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type busyEntry struct {
    end  int64
    room int
}
type busyHeap []busyEntry

func (h busyHeap) Len() int { return len(h) }
func (h busyHeap) Less(i, j int) bool {
    if h[i].end != h[j].end {
        return h[i].end < h[j].end
    }
    return h[i].room < h[j].room
}
func (h busyHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *busyHeap) Push(x interface{}) { *h = append(*h, x.(busyEntry)) }
func (h *busyHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mostBooked(n int, meetings [][]int) int {
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
    freeRooms := &intHeap{}
    for i := 0; i < n; i++ {
        *freeRooms = append(*freeRooms, i)
    }
    heap.Init(freeRooms)
    busy := &busyHeap{}
    count := make([]int, n)
    for _, m := range meetings {
        s, e := int64(m[0]), int64(m[1])
        for busy.Len() > 0 && (*busy)[0].end <= s {
            top := heap.Pop(busy).(busyEntry)
            heap.Push(freeRooms, top.room)
        }
        if freeRooms.Len() > 0 {
            r := heap.Pop(freeRooms).(int)
            heap.Push(busy, busyEntry{e, r})
            count[r]++
        } else {
            top := heap.Pop(busy).(busyEntry)
            heap.Push(busy, busyEntry{top.end + (e - s), top.room})
            count[top.room]++
        }
    }
    best := 0
    for i := 1; i < n; i++ {
        if count[i] > count[best] {
            best = i
        }
    }
    return best
}

import heapq
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        free_rooms = list(range(n))
        heapq.heapify(free_rooms)
        busy: List[tuple] = []  # (end_time, room)
        count = [0] * n
        for s, e in meetings:
            while busy and busy[0][0] <= s:
                _, r = heapq.heappop(busy)
                heapq.heappush(free_rooms, r)
            if free_rooms:
                r = heapq.heappop(free_rooms)
                heapq.heappush(busy, (e, r))
                count[r] += 1
            else:
                end, r = heapq.heappop(busy)
                heapq.heappush(busy, (end + (e - s), r))
                count[r] += 1
        best = 0
        for i in range(1, n):
            if count[i] > count[best]:
                best = i
        return best

class Heap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
                if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function mostBooked(n, meetings) {
    meetings.sort((a, b) => a[0] - b[0]);
    const freeRooms = new Heap((a, b) => a - b);
    for (let i = 0; i < n; i++) freeRooms.push(i);
    // busy: [end, room]
    const busy = new Heap((a, b) => a[0] - b[0] || a[1] - b[1]);
    const count = new Array(n).fill(0);
    for (const [s, e] of meetings) {
        while (busy.size() > 0 && busy.peek()[0] <= s) {
            const [, r] = busy.pop();
            freeRooms.push(r);
        }
        if (freeRooms.size() > 0) {
            const r = freeRooms.pop();
            busy.push([e, r]);
            count[r]++;
        } else {
            const [end, r] = busy.pop();
            busy.push([end + (e - s), r]);
            count[r]++;
        }
    }
    let best = 0;
    for (let i = 1; i < n; i++) if (count[i] > count[best]) best = i;
    return best;
}

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> freeRooms = new PriorityQueue<>();
        for (int i = 0; i < n; i++) freeRooms.offer(i);
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) ->
            a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        int[] count = new int[n];
        for (int[] m : meetings) {
            long s = m[0], e = m[1];
            while (!busy.isEmpty() && busy.peek()[0] <= s) {
                long[] top = busy.poll();
                freeRooms.offer((int) top[1]);
            }
            if (!freeRooms.isEmpty()) {
                int r = freeRooms.poll();
                busy.offer(new long[]{e, r});
                count[r]++;
            } else {
                long[] top = busy.poll();
                busy.offer(new long[]{top[0] + (e - s), top[1]});
                count[(int) top[1]]++;
            }
        }
        int best = 0;
        for (int i = 1; i < n; i++) if (count[i] > count[best]) best = i;
        return best;
    }
}

class Heap<T> {
    private h: T[] = [];
    constructor(private cmp: (a: T, b: T) => number) {}
    size(): number { return this.h.length; }
    peek(): T { return this.h[0]; }
    push(v: T): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): T {
        const top = this.h[0];
        const last = this.h.pop() as T;
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
                if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function mostBooked(n: number, meetings: number[][]): number {
    meetings.sort((a, b) => a[0] - b[0]);
    const freeRooms = new Heap<number>((a, b) => a - b);
    for (let i = 0; i < n; i++) freeRooms.push(i);
    // busy: [end, room]
    const busy = new Heap<[number, number]>((a, b) => a[0] - b[0] || a[1] - b[1]);
    const count: number[] = new Array(n).fill(0);
    for (const [s, e] of meetings) {
        while (busy.size() > 0 && busy.peek()[0] <= s) {
            const [, r] = busy.pop();
            freeRooms.push(r);
        }
        if (freeRooms.size() > 0) {
            const r = freeRooms.pop();
            busy.push([e, r]);
            count[r]++;
        } else {
            const [end, r] = busy.pop();
            busy.push([end + (e - s), r]);
            count[r]++;
        }
    }
    let best = 0;
    for (let i = 1; i < n; i++) if (count[i] > count[best]) best = i;
    return best;
}