@@ -0,0 +1,1970 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.Arrays;%0Aimport java.util.PriorityQueue;%0A%0A/**%0A * Given an array of meeting time intervals consisting of start and end times %5B%5Bs1,e1%5D,%5Bs2,e2%5D,...%5D (si %3C ei), find the%0A * minimum number of conference rooms required.%0A * %3Cp%3E%0A * For example,%0A * Given %5B%5B0, 30%5D,%5B5, 10%5D,%5B15, 20%5D%5D,%0A * return 2.%0A * %3Cp%3E%0A * Company Tags: Google Facebook%0A * Tags: Heap, Greedy, Sort%0A * Similar Problems: (H) Merge Intervals (E) Meeting Rooms%0A */%0Apublic class MeetingRooms2 %7B%0A%0A    public class Solution %7B%0A%0A        /**%0A         * Sort, heap, greedy.%0A         * Always put the next starting meeting after the first ending meeting.%0A         * If the start time overlaps with the nearest end time, need a new room.%0A         * So, sort the meetings according to start time first.%0A         * Then for each interval in the array:%0A         * 1) If min heap is empty, add to heap directly.%0A         * 2) Compare with the min ending time, if doesn't overlap, add this meeting after.%0A         * 3) If overlap, need a new room.%0A         */%0A        public int minMeetingRooms(Interval%5B%5D intervals) %7B%0A            if (intervals == null %7C%7C intervals.length == 0) %7B%0A                return 0;%0A            %7D%0A            Arrays.sort(intervals, (a, b) -%3E a.start - b.start);%0A            PriorityQueue%3CInterval%3E minHeap = new PriorityQueue%3C%3E(intervals.length, (a, b) -%3E a.end - b.end);%0A            for (Interval i : intervals) %7B%0A                if (!minHeap.isEmpty() && i.start %3E= minHeap.peek().end) %7B%0A                    minHeap.poll();%0A                %7D%0A                minHeap.add(i);%0A            %7D%0A            return minHeap.size();%0A        %7D%0A    %7D%0A%0A    /**%0A     * Interval class provided by leetcode.%0A     */%0A    public class Interval %7B%0A%0A        int start;%0A        int end;%0A%0A        Interval() %7B%0A            start = 0;%0A            end = 0;%0A        %7D%0A%0A        Interval(int s, int e) %7B%0A            start = s;%0A            end = e;%0A        %7D%0A    %7D%0A%7D%0A

add meeting rooms 2