扫描线

Meeting Room II

• create 2 separate arrays, starts[] and ends[] to store startPointer and endPointer

• sort both in increasing order

• while(i < len && j < len)

• if starts[i] >= ends[j], room-- and j++

• else room++ and i++

• return max(room)

private int sweepLine(int[][] intervals) {
        //create 2 separate arrays, starts[] and ends[], sort both in increasing order
        //while loop starts
        //if starts[i] >= ends[j], room-- and j++
        //else room ++ and i++
        //return max(room)
        int len = intervals.length;
        int[] starts = new int[len], ends = new int[len];
        for (int i = 0; i < len; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int i = 0, j = 0, room = 0, minRoom = 0;
        while (i < len && j < len) {
            if (starts[i] >= ends[j]) {
                room--;
                j++;
            } else {
                room++;
                minRoom = Math.max(minRoom, room);
                i++;
            }
        }
        return minRoom;
    }