Facebook面试题 meeting rooms 求同时最多meeting room的时间

超、凢脫俗 2022-07-13 11:26 100阅读 0赞

> 给出会议开始和结束时间，求meeting room interval最多的时间点。返回任意一个时间即可。

*  显然本题可以方便地使用扫描线算法解决。在扫描线段的同时保存一个时间。最终返回最多interval对应的时间即可。整个算法可以描述如下：  
    
    
    1.  将meeting开始和结束的时间点分别存在list中。
    2.  对整个list按时间排序。相同的时间结束应该优先于开始。
    3.  遍历排序好的list，对同时存在的线段进行计数并记录时间。

`O(nlogn)`时间，`O(n)`空间。因为我们最多对`2n`个点进行了存储，排序和遍历。

算法的Java实现如下：

/**
     * Definition of Interval:
     * public class Interval {
     *  int start, end;
     *  Interval(int start, int end) {
     *      this.start = start;
     *      this.end = end;
     *  }
     * }
     */
    
    
    class Point {
        int time;
        int flag;
    
        public Point(int time, int flag) {
            this.time = time;
    
            //end flag = 0, start flag = 1
            this.flag = flag;
        }
    
        public static Comparator<Point> PointComparator = new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.time == p2.time) {
                    return p1.flag - p2.flag; // end has priority over start
                }
                return p1.time - p2.time;
            }
        };
    }
    
    class Solution {
        public int timeWithMostIntervals(List<Interval> meetings) {
            if (meetings == null || meetings.size() == 0) {
                return 0;
            }
    
            List<Point> lines = new ArrayList<meetings.size() * 2>();
            for (Interval i : meetings) {
                lines.add(i.start, 1);
                lines.add(i.end, 0);
            }
    
            Collections.sort(lines, Point.PointComparator);
    
            int ret = 0;
            int max = Integer.MIN_VALUE;
            int count = 0;
            for (int i = 0; i < lines.size(); i++) {
                if (lines.get(i).flag == 0) {
                    count--;
                }
                else {
                    count++;
                }
    
                if (count > max) {
                    max = count;
                    ret = lines.get(i).time;
                }
            }
    
            return ret;
        }
    }