Easy to understand Java solution with O(N) and NO heap NO map needed


  • 4

    I come up this idea with the help of : https://discuss.leetcode.com/topic/30610/super-easy-java-solution-beats-98-8/2
    However, I think my solution is O(n), cheaper than O(N logN)

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if(intervals.length == 0) return 0;
            int maxtime = Integer.MIN_VALUE;
            //Find max meeting time
            for(int i = 0; i < intervals.length; i++){
                maxtime = Math.max(maxtime, intervals[i].end);
            }
            int[] cont = new int[maxtime+1];
            for(int i = 0; i < intervals.length; i++){
                cont[intervals[i].start]++;
                cont[intervals[i].end]--;
            }
            int res = 0;
            for(int i = 1; i <= maxtime; i++){
                cont[i] += cont[i-1];
                res = Math.max(res, cont[i]);
            }
            return res;
        }
    }
    

  • 0

    What a nice solution I never see!!!


  • 0
    Z

    counting sort, nice one!


Log in to reply
 

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