会议室

#富途一面算法题#

ps：leetcode需要开通会员，才能刷这道题目。

一、题目描述

　　给一个会议时间安排的数组intervals，每个会议室包含开始时间和结束时间，即intervals[i] = [starti, endi]，为避免会议冲突，同时要考虑充分利用会议室资源，至少需要多少间会议室，才能满足这里会议安排。

二、示例

用例1

输入：intervals = [[0,30], [5, 10], [15,20]]

输出：2

用例2

输入：intervals = [[7,10], [2,4]]

输出：1

三、解题思路

　　这道题可以转化为上下公交车问题一样，每个人上车的时间不同，即开始时间，在下车的时间也不同，即结束时间，求得在车上最多人数。

　　这道题可以用暴力算法，但面试官眉头一皱。所以这道题目需要用最优解法，即贪心算法。可以转化为坐标形式，通过垂直于x轴从左向右移动，移动过程中，记录这根线与区间的最大交点个数，即相交的最大区间个数。

四、代码实现

 1  1 var minMeeting = function(intervals) {
 2  2   const nums = [];
 3  3   // 存放数据，上车+1，下车-1
 4  4   for(let [up, down] of intervals) {
 5  5     nums.push([up, 1]);
 6  6     nums.push([down, -1]);
 7  7   }
 8  8   // 排序：首先按时间，时间相同的，先下车，后上车
 9  9   nums.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
10 10   // 遍历数组，找到最大的相交点
11 11   let res = 0;
12 12   let curValue = 0
13 13   for(let [value, flag] of nums) {
14 14     curValue += flag;
15 15     res = Math.max(res, curValue);
16 16   }
17 17   return res;
18 18 }