super easy-to-understand scan line algorithm


  • 0
    class Solution {
        static class timePoint {
            int time;
            int type;
    
            public timePoint(int time, int type) {
                this.time = time;
                this.type = type;
            }
    
            public static Comparator<timePoint> PointComparator  = new Comparator<timePoint>(){
                public int compare(timePoint p1, timePoint p2){
                    if(p1.time == p2.time) return p1.type - p2.type;
                    else return p1.time - p2.time;
                }
            };
        }
    
    
        public static int minMeetingRooms(Interval[] intervals) {
    
            List<timePoint> allTimePoint = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                allTimePoint.add(new timePoint(intervals[i].start, 1));
                allTimePoint.add(new timePoint(intervals[i].end, 0));
            }
    
            Collections.sort(allTimePoint, timePoint.PointComparator);
    
            int currentCount = 0;
            int maxOverlap = 0;
    
            for (timePoint i : allTimePoint) {
                if (i.type == 1)
                    currentCount ++;
                else
                    currentCount --;
    
                maxOverlap = Math.max(currentCount, maxOverlap);
            }
            return maxOverlap;
        
        }
    }
    

Log in to reply
 

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