5ms mergeSort idea


  • 0
    Q

    Sort start time of the meetings and sort end time of the meetings, since start time of the same meeting is always < end time. We don't need to remember which end time or start time correspond to which meeting.
    Merge start time array and end time array, when start time is small, add meeting room count, if end time small, subtract meeting room count; remember the max Count;

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if(intervals.length == 0){
                return 0;
            }
            int[] sta = new int[intervals.length];
            int[] eda = new int[intervals.length];
            for(int i = 0; i < intervals.length; ++i){
                sta[i] = intervals[i].start;
                eda[i] = intervals[i].end;
            }
            Arrays.sort(sta);
            Arrays.sort(eda);
            int stptr = 0, edptr = 0;
            int cnt = 0, mCnt = Integer.MIN_VALUE;
            while(stptr < sta.length && edptr < eda.length){
                if(sta[stptr] < eda[edptr]){
                    stptr++;
                    cnt++;
                }
                else if(sta[stptr] > eda[edptr]){
                    edptr++;
                    cnt--;
                }
                else{
                    stptr++;
                    edptr++;
                }
                mCnt = (cnt > mCnt) ? cnt : mCnt;
            }
            return mCnt;
        }
    }

Log in to reply
 

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