Sort and count max concurrent on-going meetings.


  • 0
    Z
    /**
     * Extrat start and end time from each interval, put them into Node, sort them together in one array. 
     * Find max concurrent on-going meeting count, similar to counting open paranthes in valid paranthes problem.
     */ 
    public class Solution {
        public int minMeetingRooms(Interval[] ins) {
            /*extract start and end, put them in one list and sort alltogether*/
            List<Node> all = new ArrayList<>();
            
            for(Interval in: ins){
                all.add(new Node(in.start, false));
                all.add(new Node(in.end, true));
            }
            
            all.sort(null); // sort using natural order, which uses compareTo()
            
            /*find count of concurrent on-going meeting*/
            int count = 0;
            int max =0;
            for(Node n: all){
                if(n.isEnd){
                    count --;
                }
                else{
                    count ++;
                    max = Math.max(count, max);
                }
            }
            
            return max;
        }
        
        private static class Node implements Comparable<Node>{
            int val;
            boolean isEnd;
            
            Node(int val, boolean end){
                this.val = val;
                this.isEnd = end;
            }
            
            // ascending val sort; ending before starting.
            public int compareTo(Node other){
                int diff = this.val - other.val;
                
                return diff != 0 ? diff : (this.isEnd ? -1: 1);
                
            }
        }
    }

Log in to reply
 

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