Meeting Rooms变种

// Question1: 给出需要使用最多房间的具体时间

public class MeetingRoomsII {
	public List<Integer> minMeetingRooms(Interval[] intervals) {
		List<int[]> order = new ArrayList<>();
		for (Interval interval : intervals) {
			order.add(new int[]{interval.start, 1});
			order.add(new int[]{interval.end, -1});
		}
		Collections.sort(order, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				if(a[0] == b[0]) {
					return a[1] - b[1];
				} else {
					return a[0] - b[0];
				}
			}
		});
		
		List<int[]> periods = new ArrayList<int[]>();  // 最大count的时间段的集合
		int max = 0, num = 0, start = 0;
		for(int[] pos : order) {
			if(pos[1] == 1) {   // start point
				num ++;
				start = pos[0];
			} else {           // end point
				if(num == max) {
					periods.add(new int[]{start, pos[0]});
				} else if(num > max) {
					max = num;
					periods = new ArrayList<>();
					periods.add(new int[]{start, pos[0]});
				}
				num --;
			}
		}
		
		List<Integer> result = new ArrayList<Integer>();
		for(int[] period : periods) {
			for(int i=period[0]; i<= period[1]; i++) {
				result.add(i);
			}
		}
		System.out.println("max number is: " + max);
		return result;
	}
	
	public static void main(String[] args) {
		MeetingRoomsII test = new MeetingRoomsII();
		Interval i1 = new Interval(1,5);
		Interval i2 = new Interval(3, 8);
		Interval i3 = new Interval(6, 10);
		Interval[] intervals = {i1, i2, i3};
		List<Integer> result = test.minMeetingRooms(intervals);
		for(int time : result) {
			System.out.print(time + " ");
		}
	}
}

// Question 2:
公司里有好多employee，给出入职和离职的时间段，打印出每个时间段的在职人数
输入：
［1, 2005, 2016］
［2, 2008, 2014］
［3, 2006, 2008］
［4, 2010, 2014］
输出:
2005-2006: 1
2006-2008: 2
2008-2010: 2
2010-2014: 3
2014-2016: 1

public class EmployeeNumbers {
	public static void printEmployeeNumbers(Employee[] employees) {
		if(employees == null || employees.length == 0) return;
		List<int[]> order = new ArrayList<int[]>();
		for(Employee employee : employees) {
			order.add(new int[]{employee.start, 1});
			order.add(new int[]{employee.end, -1});
		}
		Collections.sort(order, new Comparator<int[]>() {
			public int compare(int[] i1, int[] i2) {
				if(i1[0] == i2[0]) {
					return i1[1] - i2[1];
				} else {
					return i1[0] - i2[0];
				}
			}
		});
		
		int num = 1;
		int left = order.get(0)[0];
		for(int i=1; i<order.size(); i++) {
			int[] time = order.get(i);
			if(time[0] != left) {
				System.out.println(left + "-" + time[0] + ": " + num);
				left = time[0];
			}
			if(time[1] == 1) {
				num ++;
			} else {
				num --;
			}
		}
		if(order.get(order.size()-1)[0] != left) {
			System.out.println(left + "-" + order.get(order.size()-1)[0] + ": " + num);
		}
	}
	
	public static void main(String[] args) {
		Employee e1 = new Employee(1, 2005, 2016);
		Employee e2 = new Employee(1, 2008, 2014);
		Employee e3 = new Employee(1, 2006, 2008);
		Employee e4 = new Employee(1, 2010, 2014);
		Employee[] employees = {e1, e2, e3, e4};
		printEmployeeNumbers(employees);
	}
}

class Employee {
	int id;
	int start;
	int end;
	public Employee(int id, int start, int end) {
		this.id = id;
		this.start = start;
		this.end = end;
	}
}

// Question 3:
input: log file, <user name, login time, logout time>   
output: <time,number of users>
假定同一个user的login time, logout time 没有overlap: 

<"user a", 5,10>
<"user b", 6,8>
<"user c", 10,11>

output:
<5,1> <6,2> <8,1> <10,1> <11,0>

感觉可以把每个log file拆成两部分，放在一个class里面
比如: 
class Event {
int time,
boolean login
}

比如<"user a", 5,10>就分成
Event (5, true) 和 Event (10, false)

然后把所有Event按照时间排序
然后遍历一下，同时维护一个变量 numOfUsers
如果遇见event的login是true ，那么就 ++numOfUsers
如果是false 就 -- numOfUsers


不同场景，相同应用：
第一题
question: write a function that detects conflicts in given meeting schedules
input: N intervals, [(s1, e1), (s2, e2), ..]
output: return True if there's any conflict, False otherwise
解法：
1. sort intervals and compare, O(nlogn)
2. 开一个boolean[] array, 找出intervals里的earliest time和lastest time作为数组起始和结束。然后每个interval覆盖的区域都变成true，
再判断如果下一个interval的区域内有true出现，则有overlap

第二题
http://www.fgdsb.com/2015/01/30/meeting-rooms/
question: write a function that calculates the minimum number of rooms that can accommodate given meeting schedules
input: the same
output: # of rooms
解法：
可以建一个新的class，包含int time和boolean isStartTime, 然后将所有time排序，用一个numOfRooms计数，遇到isStartTime则+1, 否则-1,
在这个过程中记录numOfRooms的最大值