Meeting Rooms II

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto& it : intervals) {
            if (!pq.empty() && pq.top() <= it[0]) pq.pop();
            pq.push(it[1]);
        }
        return pq.size();
    }
};

import (
    "container/heap"
    "sort"
)

type minHeap []int

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

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    pq := &minHeap{}
    for _, it := range intervals {
        if pq.Len() > 0 && (*pq)[0] <= it[0] {
            heap.Pop(pq)
        }
        heap.Push(pq, it[1])
    }
    return pq.Len()
}

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        pq: List[int] = []
        for start, end in intervals:
            if pq and pq[0] <= start:
                heapq.heappop(pq)
            heapq.heappush(pq, end)
        return len(pq)

class MinHeap {
    constructor() { this.h = []; }
    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.h[p] <= this.h[i]) 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.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function minMeetingRooms(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const pq = new MinHeap();
    for (const [start, end] of intervals) {
        if (pq.size() > 0 && pq.peek() <= start) pq.pop();
        pq.push(end);
    }
    return pq.size();
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] it : intervals) {
            if (!pq.isEmpty() && pq.peek() <= it[0]) pq.poll();
            pq.offer(it[1]);
        }
        return pq.size();
    }
}

class MinHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    peek(): number { return this.h[0]; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop() as number;
        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.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function minMeetingRooms(intervals: number[][]): number {
    intervals.sort((a, b) => a[0] - b[0]);
    const pq = new MinHeap();
    for (const [start, end] of intervals) {
        if (pq.size() > 0 && pq.peek() <= start) pq.pop();
        pq.push(end);
    }
    return pq.size();
}