[leetcode]253. Meeting Rooms II 会议室II

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

 

思路

 | 0 ------------------------- 30 |

           |5-----10|

                                |15---20|

 

1.  if starts[i] > ends[endItr],  which means  current meeting starts right after, we can continue to use previous meeting room. All we need to do is update ends pointer

2. otherwies, starts[i] < ends[endItr],  which means current meeting starts when previous meeting has not ended. Then we need a new room for current meeting.

 

代码

1 class Solution { 2 public int minMeetingRooms(Interval[] intervals) { 3 int[] starts = new int[intervals.length]; 4 int[] ends = new int[intervals.length]; 5 for(int i = 0; i< intervals.length; i++) { 6 starts[i] = intervals[i].start; 7 ends[i] = intervals[i].end; 8 } 9 Arrays.sort(starts); 10 Arrays.sort(ends); 11 int rooms = 0; 12 int endsItr = 0; 13 for(int i= 0; i< starts.length; i++) { 14 if(starts[i]<ends[endsItr]) 15 rooms++; 16 else 17 endsItr++; 18 } 19 return rooms; 20 } 21 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/9808255.html

相关资源：数据结构—成绩单生成器