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;
    }
    
}