253. Meeting Rooms II

using System;
using System.Collections.Generic;
public class Solution {
    public int MinMeetingRooms(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        var heap = new SortedSet<int>();
        heap.Add(intervals[0][1]);
        
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] >= heap.Min) {
                heap.Remove(heap.Min);
            }
            heap.Add(intervals[i][1]);
        }
        return heap.Count;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinMeetingRooms(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        var heap = new SortedSet<int>();
        heap.push_back(intervals[0][1]);
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= heap.Min) {
                heap.Remove(heap.Min);
            }
            heap.push_back(intervals[i][1]);
        }
        return heap.size();
    }
}

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(intervals[0][1]);
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= heap.peek()) {
                heap.poll();
            }
            heap.add(intervals[i][1]);
        }
        return heap.size();
    }
}

class Solution {
    minMeetingRooms(intervals) {
        intervals.sort((a, b) => a[0] - b[0])
        const heap = [intervals[0][1]]
        
        for (let i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= heap[0]) {
                heap.shift()
            }
            heap.push(intervals[i][1])
            heap.sort((a, b) => a - b)
        }
        return heap.length
    }
}

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        heap = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= heap[0]:
                heapq.heapreplace(heap, intervals[i][1])
            else:
                heapq.heappush(heap, intervals[i][1])
        
        return len(heap)

package main

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[0 : n-1]
    return x
}

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    h := &MinHeap{intervals[0][1]}
    heap.Init(h)
    
    for i := 1; i < len(intervals); i++) {
        if intervals[i][0] >= (*h)[0] {
            heap.Pop(h)
        }
        heap.Push(h, intervals[i][1])
    }
    return h.Len()
}

Algorithm

1️⃣

Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

2️⃣

Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):

Если свободна, обновите время окончания этой комнаты.

Если не свободна, добавьте новое время окончания в кучу.

3️⃣

После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎