253. Meeting Rooms II

三刷
Version #3 Sort start & end at the same time

3.68 %
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        List<int[]> list = new ArrayList<>();
        for (Interval interval : intervals) {
            list.add(new int[]{interval.start, 1});
            list.add(new int[]{interval.end, -1});
        }
        Collections.sort(list, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1]; // end happens before start
            return a[0] - b[0];
        });
        int count = 0;
        int result = 0;
        for (int i = 0; i < list.size(); i++) {
            count += list.get(i)[1];
            result = Math.max(result, count);
        }
        return result;
    }
}


Version #2
sort start & end separately
用count表示现在有的meeting rooms的数量
如果有meeting结束 可以把后面的放进vacant的room
如果没有结束的meeting 就需要增加rooms的数量
81.05 %
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        int length = intervals.length;
        int[] starts = new int[length];
        int[] ends = new int[length];
        for (int i  = 0; i < length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int count = 0;
        int pEnd = 0;
        for (int pStart = 0; pStart < length; pStart++) {
            if (starts[pStart] < ends[pEnd]) {
                count++;
            } else {
                pEnd++;
            }
        }
        return count;
    }
}

Version #1 Naive Sort Intervals Version
重点是breaking tie
看到discuss里面还有用heap和分别sort start&end的方法，懒得看了

49.06 %
class Solution {
    class Tuple implements Comparable<Tuple> {
        int time;
        int isStart; //start -> 1, end -> 0
        public Tuple(int time, int isStart) {
            this.time = time;
            this.isStart = isStart;
        }
        @Override
        public int compareTo(Tuple that) {
            if (this.time != that.time) {
                return this.time - that.time;
            } else {
                return this.isStart - that.isStart;
            }
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        List<Tuple> times = new ArrayList<>();
        for (Interval i : intervals) {
            times.add(new Tuple(i.start, 1));
            times.add(new Tuple(i.end, 0));
        }
        Collections.sort(times);
        int max = 0;
        int count = 0;
        for (Tuple tuple : times) {
            if (tuple.isStart == 1) {
                count++;
                max = Math.max(count, max);
            } else {
                count--;
            }
        }
        return max;
    }
}