Problem
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
Solution
If we align the meetings in three lines, then use a vertical line to scan from left to right, the max number of intersection is our answer. For the intersection problem, we have standard solution.
We sort the time points involved, Then we iterate from left to right like we have a vertical line to scan the dots. If a time point is a start time, we increase count, if it is end time, we decrease count. The max count is our answer.
--------------------------------------------------
-------------
------------
import java.util.*;
class Solution {
public static void main(String[] args) {
int[][] input = new int[][]{
{}
};
System.out.println(solve(input));
}
private static int solve(int[][] input) {
if(input == null || input.length == 0)
return 0;
List<StartEnds> list = new ArrayList<>();
for(int[] val : input) {
if(val == null || val.length != 2)
throw new IllegalArgumentException("bad input");
list.add(new StartEnds(val[0], true));
list.add(new StartEnds(val[1], false));
}
list.sort((o1, o2) -> o1.time - o2.time);
int result = Integer.MIN_VALUE;
int count = 0;
for(StartEnds timepoint : list) {
if(timepoint.isStart)
count++;
else
count--;
result = Math.max(result, count);
}
return result;
}
static class StartEnds {
int time;
boolean isStart;
public StartEnds(int time, boolean isStart) {
this.time = time;
this.isStart = isStart;
}
}
}
The time complexity is O(NlogN) for sorting the time points.
The space complexity is O(N) for storing the time points.
