Java O(n) Solution and less Error-prone


  • 1

    The basic idea is to build a counting array like the window between the earliest start time and latest end time. Then scan the intervals array, for start time add 1 and for end time subtract 1 which is not hard to understand. The counting array represent how many meetings are held at the same time. Then by scanning the counting array we can get how many rooms are needed globally.

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) return 0;
            int maxEnd = 0;
            int minStart = Integer.MAX_VALUE;
            for (Interval interval : intervals) {
                minStart = Math.min(interval.start, minStart);
                maxEnd = Math.max(interval.end, maxEnd);
            }
            int[] buckets = new int[maxEnd - minStart + 1];
            for (Interval interval : intervals) {
                buckets[interval.start - minStart]++;
                buckets[interval.end - minStart]--;
            }
            int occupied = 0;
            int res = 0;
            for (int i = 0; i < buckets.length; i++) {
                occupied += buckets[i];
                res = Math.max(res, occupied);
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.