919 · Meeting Rooms II - LintCode

# Description

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

# Note

下面是其中一個解法是看他的時間線，就像 391・Number of Airplanes in the Sky - LintCode 一樣，用兩個數組 /list 分別記錄一下 start time 和 end time。
如果 start time 小於 end time 的話，說明之前的會議並沒有結束，所以給 room + 1。這題在 = 的情況下還沒有會議時間的衝突

假設 intervals = [(0,30),(5,10),(15,20)]

i	start time		end time	room	j
0	0	<	10	0 -> 1	0
1	5	<	10	1 -> 2	0
2	15	>	10	2	0 -> 1

到了這一步，已經把 start array 的元素看完了。只要把 start < end 的時候 room ＋ 1，其他的情況不加，然後把指針 j 移一個位就可以了。

	/**
	* Definition of Interval:
	* public class 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.isEmpty()) return 0;

	int[] start = new int[intervals.size()];
	int[] end = new int[intervals.size()];

	for (int i = 0; i < intervals.size(); i++) {
	start[i] = intervals.get(i).start;
	end[i] = intervals.get(i).end;
	}
	Arrays.sort(start);
	Arrays.sort(end);

	int max = 0, count = 0, j = 0;
	for (int i = 0; i < intervals.size(); i++) {
	if (start[i] < end[j]) { // 有 meeting 還沒有結束（overlap)
	count++;
	} // 開始時間 >= 結束時間 --> meeting 已經結束了
	// 其實寫個 else 就行
	else if (start[i] >= end[j]) {
	j++;
	}
	max = Math.max(max, count);
	}

	return max;
	}
	}

# Description

# Example

# Note

Lintcode 391 Number of Airplanes in the Sky

LC747 - Largest Number At Least Twice of Others