253. Meeting Room II

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        List<int[]> list = new ArrayList<>(intervals.length * 2);
        for (int[] i : intervals) {
            list.add(new int[]{i[0], 1});
            list.add(new int[]{i[1], -1});
        }
        list.sort((p1, p2) -> {
            if (p1[0] == p2[0]) {
                return p1[1] - p2[1];
            } else {
                return p1[0] - p2[0];
            }
        });
        int rooms = 0;
        int count = 0;
        for (int[] p : list) {
            count += p[1];
            rooms = Math.max(rooms, count);
        }
        return rooms;
    }
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null) {
            return 0;
        }
        if (intervals.length <= 1) {
            return intervals.length;
        }

        // sort the start time and the end time separately
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        int sPtr = 0;
        int ePtr = 0;
        int usedRooms = 0;
        while (sPtr < intervals.length) {
            // if a meeting is finished, reused a room
            // we don't care about which meeting is finished,
            // we care about it provided an available room.
            if (starts[sPtr] >= ends[ePtr]) {
                usedRooms--;
                ePtr++;
            }
            usedRooms++;
            sPtr++;
        }
        return usedRooms;
    }
}