AC Java code, Scan Line, O(nlogn)


  • 0
    J
    private class Meeting{
        int time;
        int type;
        Meeting(int a, int b){
            this.time = a;
            this.type = b;
        }
    }
    
     public int minMeetingRooms(Interval[] intervals) {
        if(intervals.length==0) return 0;
        ArrayList<Meeting> list = new ArrayList<Meeting>();
        for(Interval meeting : intervals){
            list.add(new Meeting(meeting.start,2));
            list.add(new Meeting(meeting.end,1));
        }
        
        Collections.sort(list,new Comparator<Meeting>(){
            public int compare(Meeting a, Meeting b){
                if (a.time==b.time) 
                    return a.type-b.type;
                return a.time-b.time;
            } 
        });
        
        int count = 0;
        int result = 0;
        for(Meeting meeting:list){
            if (meeting.type==2) count++;
            else count--;
            result = Math.max(result,count);
        }
        return result;
    }

Log in to reply
 

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