【每日一题】- 2020-04-27 - 多人运动

[azl397985856]

已知小猪每晚都要约好几个女生到酒店房间。每个女生 i 与小猪约好的时间由 [si , ei］表示，其中 si 表示女生进入房间的时间， ei 表示女生离开房间的时间。由于小猪心胸开阔，思想开明，不同女生可以同时存在于小猪的房间。请计算出小猪最多同时在做几人的「多人运动」。

例子：
Input ： [[ 0 , 30] ,[ 5 , 10 ] ， [15 , 20 ] ]
OutPut ：最多同时有两个女生的「三人运动」

类似问题：力扣会议室系列。比如：https://leetcode-cn.com/problems/meeting-rooms-ii/

[tyd2000]

#include <bits/stdc++.h>
using namespace std;
#define up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
#define girl pair<int,int>   //first开始时间,second结束时间
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const int maxn = 1001;   //小猪每晚最多约的女生数量

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;    //小猪今晚约了n个女孩
    cin >> n;
    vector<girl> v;
    up(i,1,n)
    {
        int bg,ed;
        cin >> bg >> ed;
        v.push_back(mp(bg,ed));
    }
    int cnt[maxn];    //cnt[i]记录i时刻的多人运动人数
    ms(cnt,0);
    int ans = -INF;
    up(i,0,n-1)    //枚举
    {
        up(j,v[i].first,v[i].second)
        {
            cnt[j]++;
            ans = max(ans,cnt[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

[azl397985856]

思路

直觉：

我们来看下有哪些情况，看是否可以打开思路。 如下图：

（上面的情况，那么最大的人数是1，下面的情况最大的人数是2）

不难发现，除了关心开始时间，我们应该同样关心结束时间。 如果”相邻“的区间重合，则人数++，最后返回人数即可。

本质上是枚举和当前女孩一起多人运动的人数的最大值，当前女孩一起多人运动的就是不比当前女孩晚进场且要排除掉结束时间大于当前女孩开始时间。

要不要考虑比当前女孩晚进场，但是在女孩离开前进场的呢？不需要，因此枚举到那个女孩的时候，会考虑这种情况。

因此按照进场时间排序，然后用堆来排除结束时间大于进场时间的，就不难想到了。

具体算法：

• 按照女孩约会的开始时间进行一次升序排序

• 然后用一个小顶堆，维护当前每个女孩约会的结束时间
  
• 然后当一个新的女孩出现的时候则入堆，并判断一下是否和上一个女孩有重叠。没有重叠的话（人数不变），我们可以弹出一个元素，保持堆的人数不变。
• 堆的大小表示的就是多人运动的最大人数，返回堆的大小即可。

代码

C++ 代码：

class Solution {
public:
    int solve(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>&b){
            return a[0] < b[0];
        });
        priority_queue<int, vector<int>, greater<int>> heap;
        int ans = 0;
        for (int i = 0; i < intervals.size(); i++) {
            // 没重叠，弹出堆顶元素，并维持最小堆的性质不变
            if (!heap.empty() && heap.top() <= intervals[i][0]) {
                heap.pop();
            }
            // 女孩++
            heap.push(intervals[i][1]);
           ans = max(ans, heap.size())
        }
        return ans;
    }
};

Python3 代码：

class Solution:
    def solve(self, intervals):
        intervals.sort(key=lambda x:x[0])
        h = []
        ans = 0
        for fr, to in intervals:
            if h and h[0] <= fr:
                heapq.heappop(h)
            heapq.heappush(h, to)
            ans = max(ans, len(h))
        return ans

另外一种解法

将区间离散化为若干点。比如 [1,3] 变为 [1, 0] [3, 1]，其中 0 表示进入， 1 表示出。

转换后对数组进行排序， 然后遍历排序后的转化数组，遇到 0 girl + 1, 遇到 1 girl - 1，一边遍历一遍维护 girl 的全局最大值即可。

参考题目：

• https://leetcode.cn/problems/meeting-rooms-ii/
• https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/description/

相关题目

力扣的会议室系列大家可以做一下，和这个很类似。

推荐一个 BS 上的题目（据说是 amazon 的面试题），简直和这道题一模一样。

• Movie-Theatres

[woshiZS]

/*Brute force is the best algorithm!*/
#include<vector>
#include<iostream>

using std::cout;
using std::endl;
class Solution{
public:
    int maxOnlineAmount(vector<vector<int>>& nums){
        int min=INT_MAX,max=INT_MIN,ans=0;
        for(auto num:nums){
            min=num[0]<min?num[0]:min;
            max=num[1]>max?num[1]:max;
        }
        vector<int> timetable(max-min+1,0);
        for(auto num:nums){
            for(int i=num[0];i<num[1];i++)timetable[i]++;
        }
        return *std::max_element(std::begin(timetable),std::end(timetable));
    }
};
int main(){
    vector<vector<int>> nums{{0,30},{5,10},{15,20},{17,25}};
    Solution solu;
    cout<<solu.maxOnlineAmount(nums)<<endl;
    return 0;
} 

[hipi]

js

const mlc = (arr) => {
    const flatArr = arr.flat()
    const minT = Math.min(...flatArr)
    const maxT = Math.max(...flatArr)
    let TIME_PEOPLE_NUM = []
    arr.forEach((pt) => {
        for (let i = minT; i <= maxT; i++) {
            if (i >= pt[0] && i <= pt[1]) {
                TIME_PEOPLE_NUM[i] ? TIME_PEOPLE_NUM[i]++ : TIME_PEOPLE_NUM[i] = 1
            }
        }
    });
    return Math.max(...TIME_PEOPLE_NUM)
}
console.log(mlc([[0, 30], [5, 10], [8, 10], [15, 20], [10, 40]]))

不知道对不对，主要是想答下(狗头)

[xfxhn]

function num(arr) {
    const nums = arr.sort((a, b) => a[0] - b[0]);
    return nums.reduce((peoples, item) => {
        if (peoples.length && peoples[peoples.length - 1] <= item[0]) {
            peoples.pop();
        }
        peoples.push(item[1]);
        console.log(peoples)
        return peoples
    }, []).length
}

[EthanLiangX]

package main

import (
	"fmt"
)

func main() {

	fmt.Println(maximalSquare([][]int{{0, 30}, {5, 10}, {8, 10}, {15, 20}, {10, 40}}))
}


func maximalSquare(matrix [][]int) int {
	var (
		maxCount = 0
	)

	f := func(n int, leave int, comeIn int) int {
		count := 1
		for i := 0; i < n; i++ {
			if comeIn <= matrix[i][1] {
				count++
			}
		}
		return count
	}
	for i := 1; i < len(matrix); i++ {
		if f(i, matrix[i][1], matrix[i][0]) > maxCount {
			maxCount = f(i, matrix[i][1], matrix[i][0])
		}
	}
	return maxCount + 1 // 算上小猪本人 +1
}

// 不知道是否符合

[LeisureGong]

Java

---

	/**
	 * 对开始时间进行排序，如果相邻的时间没有重叠，则移除最早的那个时间
	 * 堆的大小即为最大并集
	 * （移除一个元素的同时也加入一个新元素,除非有新的更大size的并集，堆的大小才会改变）
	 * @param intervals [开始时间，结束时间]二维数组
	 * @return 最大的并集
	 * @date 2020/4/28
	 */
	public int maxCount(int[][] intervals){
		// 根据开始时间排序
		Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
		// 小顶堆，保存结束时间
		PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
		for(int i = 0;i < intervals.length;i++){
			//相邻时间没有重叠，则移除最早的结束时间
			if(!minHeap.isEmpty() && minHeap.peek() <= intervals[i][0]){
				minHeap.remove();
			}
			minHeap.add(intervals[i][1]);
		}
		return minHeap.size();
	}

[suukii]

思路

1. Sort the girls by their arrive times in ascending order. Assume that all girls don't have to leave the room after they enter it until the next girl arrives and the former's leaving time has already passed.

2. Now the girls start walking into the room one by one according to their arrive times. When a girl is about to enter the room, the last girl has to check her schedule, and if she finds out that she has to take leave, she leaves the room. And the girl who arrived before her has to check her schedule too. This process goes on till all the girls left in the room are to stay according to their schedules or there's no girl left in the room, then the above mentioned girl can go into the room.

3. While the girls are entering and leaving the room, we keep a counter that records the maximum of the total number of girls staying in the room.

图解

代码

const bc = girls => {
    girls.sort((a, b) => a[0] - b[0]);

    const room = [];
    let count = 0;
    girls.forEach(g => {
        while (room.length > 0 && room[room.length - 1][1] <= g[0]) {
            room.pop();
        }
        room.push(g);
        room.sort((a, b) => b[1] - a[1])
        count = Math.max(count, room.length);
    });
    return `最多同时有${count}个女生的「${count + 1}人运动」`;
};

更正

+room.sort((a, b) => b[1] - a[1])

实际上准备要进房间的女生应该是要和房间里结束时间最早的女生比较，所以每次有新的女生进入房间后，都要对房间内的女生进行排序，让结束时间早的女生排到栈顶。这样果然还是用小顶堆最适合。

const bc = girls => {
    // 以开始时间排序
    girls.sort((a, b) => a[0] - b[0]);
    // 以结束时间建小顶堆
    const heap = new MinHeap([]);
    girls.forEach(([begin, end]) => {
        while (heap.size() && heap.peek() <= begin) {
            heap.pop();
        }
        heap.insert(end);
    });
    return heap.size();
};

class Heap {
    constructor(list = []) {
        this.list = list;
        this.init();
    }

    init() {
        const size = this.size();
        for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
            this.heapify(this.list, size, i);
        }
    }

    insert(n) {
        this.list.push(n);
        const size = this.size();
        for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
            this.heapify(this.list, size, i);
        }
    }

    pop() {
        const last = this.list.pop();
        if (this.size() === 0) return last;
        const returnItem = this.list[0];
        this.list[0] = last;
        this.heapify(this.list, this.size(), 0);
        return returnItem;
    }

    peek() {
        return this.list[0];
    }

    size() {
        return this.list.length;
    }
}
class MinHeap extends Heap {
    constructor(list) {
        super(list);
    }

    heapify(arr, size, i) {
        let smallest = i;
        const left = Math.floor(i * 2 + 1);
        const right = Math.floor(i * 2 + 2);
        if (left < size && arr[smallest] > arr[left]) smallest = left;
        if (right < size && arr[smallest] > arr[right]) smallest = right;

        if (smallest !== i) {
            [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
            this.heapify(arr, size, smallest);
        }
    }
}

[azl397985856]

@suukii 非常棒的题解， 仅次于小哥哥我啦。

你的代码中关于stack 部分， 本质上是一个单调递减栈。 而由于每一个女孩入栈出栈次数最多一次。 因此时间复杂度是$O(N^2)$。而采用堆的做法，可以以更小的代价获取到最小值（即你的栈顶）。因此从时间复杂度上来说，采用堆的算法复杂度更加优秀。

以上

[suukii]

@azl397985856 唔...谢谢 lucifer 小哥哥的夸奖，我会继续努力向“更加优秀”的小哥哥靠近的，嗯。