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
Example1
Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)
Example2
Input: intervals = [(2,7)]
Output: 1
Explanation:
Only need one meeting room
Code (Java):/** * Definition of Interval: * public classs Interval { * int start, end; * Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */ public class Solution { /** * @param intervals: an array of meeting time intervals * @return: the minimum number of conference rooms required */ public int minMeetingRooms(List<Interval> intervals) { if (intervals == null || intervals.size() == 0) { return 0; } List<Event> events = new ArrayList<>(); for (Interval interval : intervals) { events.add(new Event(interval.start, 0)); events.add(new Event(interval.end, 1)); } Collections.sort(events, new MyEventComparator()); int ans = 0; int activeMeetings = 0; for (Event event : events) { if (event.flag == 0) { activeMeetings++; } else { activeMeetings--; } ans = Math.max(ans, activeMeetings); } return ans; } } class Event { int time; int flag; // 0 start, 1 end public Event(int time, int flag) { this.time = time; this.flag = flag; } } class MyEventComparator implements Comparator<Event> { @Override public int compare(Event a, Event b) { if (a.time != b.time) { return a.time - b.time; } return b.flag - a.flag; } }
No comments:
Post a Comment