lintcode - 1897 · Meeting Room III
https://www.lintcode.com/problem/1897/?utm_source=sc-libao-zyq
line sweep + presum
[[1,2],[4,5],[8,10]]
1
[[2,3],[3,4]]
sum[i]: [0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0] (mark 1 or 0
sum[i]: [0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 0] (do presum
time : O( max timeEnd), but get ask result is O(1)
space: O(50050)
public class Solution {
/**
* @param intervals: the intervals
* @param rooms: the sum of rooms
* @param ask: the ask
* @return: true or false of each meeting
*/
public boolean[] meetingRoomIII(int[][] intervals, int rooms, int[][] ask) {
boolean[] res = new boolean[ask.length];
int[] sum = new int[50050];
int[] times = new int[50050];
int timeEnd = 0;
for (int[] interval : intervals) {
int start = interval[0];
int end = interval[1];
times[start]++;
times[end]--;
timeEnd = Math.max(timeEnd, end); // update max time end
}
// update max time end
for (int[] a : ask) {
timeEnd = Math.max(timeEnd, a[1]);
}
// mark in sum[i] this time index is a empty room
int temp = 0;
for (int i = 1; i < timeEnd; i++) {
temp += times[i];
sum[i] = (temp < rooms) ? 0 : 1;
}
System.out.println(Arrays.toString(Arrays.copyOf(sum, 11)));
for (int i = 1; i < timeEnd; i++) {
sum[i] += sum[i-1];
}
System.out.println(Arrays.toString(Arrays.copyOf(sum, 11)));
for (int i = 0; i < ask.length; i++) {
int start = ask[i][0];
int end = ask[i][1];
res[i] = (sum[start - 1] == sum[end - 1]);
}
return res;
}
}
Last updated