LeetCode [253] Meeting Rooms II

 253. Meeting Rooms II

Medium

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

//C++: 584ms bool myComp(const Interval &a, const Interval &b){ return (a.start<b.start); } class Solution { public: int minMeetingRooms(vector<interval>& intervals) { int rooms = 0; priority_queue<int> pq;//prioritize earlier ending time sort(intervals.begin(), intervals.end(), myComp); for(int i=0; i<intervals.size(); ++i){ while(!pq.empty() && -pq.top()<intervals[i].end) pq.pop(); pq.push(-intervals[i].end); rooms = max(rooms, (int)pq.size()); } return rooms; } }; //C++ //C++: 616ms /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: int minMeetingRooms(vector<Interval>& intervals) { map<int, int> changes;//sorted by keys. for(auto i:intervals){ changes[i.start]++; changes[i.end]--; } int rooms = 0, min_rooms = 0; for(auto c:changes){ rooms += c.second; min_rooms = max(min_rooms, rooms); } return min_rooms; } }; class Solution { public int minMeetingRooms(int[][] intervals) { TreeMap<Integer, Integer> map = new TreeMap<>(); for(int i=0; i<intervals.length; ++i){ map.put(intervals[i][0], map.getOrDefault(intervals[i][0], 0)+1); map.put(intervals[i][1], map.getOrDefault(intervals[i][1], 0)-1); } int rooms = 0, minRooms = 0; for(Map.Entry<Integer,Integer> e : map.entrySet()){ rooms += e.getValue(); minRooms = Math.max(minRooms, rooms); } return minRooms; } }

YMSF

第二轮，白人manager，刷题网尔无伞的变形，要求自定义输入的数据，并且返回一个schedule（自定义输出格式）。我这轮执着于原题解法，总是想用priority queue，写的磕磕巴巴，面完回去想了想用dict记录每个房间和能放在这个房间的所有会议起始时间就行。。最后问了问怎么测试，测试数据从哪来。。等等，就到时间了，这轮应该是给了个比较差的feedback。