Given N groups of people who want to have a meeting in the only meeting room in the office. Each group has people[i] people, who want to start the meeting at the starting[i] time and end it at the ending[i] time (both inclusive).
No two groups can use the meeting room at the same time, If group j does not get the meeting room, then all the people[i] people cannot meet.
Calculate the minimum number of people that cannot meet if the meeting room is optimally assigned to groups.
Note: Group i and j can get the meeting room one after the other if and only if end[i] Input Format: • The first line contains Ndenoting the number of groups. • The second line containsNspace-separated integers denoting the number of people in each group • The third line containsNspace-separated integers denoting the starting time of each group's meeting • The fourth line containsN` space-separated integers denoting the ending time of each group's meeting
Constraints
N/A
解法
区间加权选择不重叠子集(weighted interval scheduling，使其包含人数最多)，未被选的人数累加即为答案。把每个 group 看成 (start, end, people)，按 end 升序排序，dp[i] 表示考虑前 i 个区间能容纳的最大人数：dp[i] = max(dp[i-1], dp[p(i)] + people[i])，p(i) 是 end ≤ start[i]-1 的最大下标，二分查找。最少不能开会人数 = sum(people) - dp[n]。时间 O(N log N)，空间 O(N)。
from typing import List
import bisect
def meetingRoom(N: int, people: List[int], starting: List[int], ending: List[int]) -> int:
groups = sorted(zip(ending, starting, people))
ends = [g[0] for g in groups]
dp = [0] * (N + 1)
for i in range(1, N + 1):
e_i, s_i, p_i = groups[i - 1]
# find largest j such that ends[j-1] < s_i
lo, hi = 0, i - 1
while lo < hi:
mid = (lo + hi + 1) // 2
if ends[mid - 1] < s_i:
lo = mid
else:
hi = mid - 1
dp[i] = max(dp[i - 1], dp[lo] + p_i)
return sum(people) - dp[N]import java.util.*;
class Solution {
int meetingRoom(int N, int[] people, int[] starting, int[] ending) {
Integer[] idx = new Integer[N];
for (int i = 0; i < N; i++) idx[i] = i;
Arrays.sort(idx, (x, y) -> ending[x] - ending[y]);
int[] s = new int[N], e = new int[N], p = new int[N];
for (int i = 0; i < N; i++) {
s[i] = starting[idx[i]];
e[i] = ending[idx[i]];
p[i] = people[idx[i]];
}
int[] dp = new int[N + 1];
int total = 0;
for (int v : people) total += v;
for (int i = 1; i <= N; i++) {
int lo = 0, hi = i - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (e[mid - 1] < s[i - 1]) lo = mid;
else hi = mid - 1;
}
dp[i] = Math.max(dp[i - 1], dp[lo] + p[i - 1]);
}
return total - dp[N];
}
}#include <vector>
#include <algorithm>
#include <numeric>
class Solution {
public:
int meetingRoom(int N, std::vector<int>& people, std::vector<int>& starting, std::vector<int>& ending) {
std::vector<int> idx(N);
std::iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(), [&](int x, int y) { return ending[x] < ending[y]; });
std::vector<int> s(N), e(N), p(N);
for (int i = 0; i < N; i++) {
s[i] = starting[idx[i]];
e[i] = ending[idx[i]];
p[i] = people[idx[i]];
}
std::vector<int> dp(N + 1, 0);
int total = 0;
for (int v : people) total += v;
for (int i = 1; i <= N; i++) {
int lo = 0, hi = i - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (e[mid - 1] < s[i - 1]) lo = mid;
else hi = mid - 1;
}
dp[i] = std::max(dp[i - 1], dp[lo] + p[i - 1]);
}
return total - dp[N];
}
};In a shop with N counters, M people arrive for billing at different times denoted as time[i]. Each person selects the counter with the shortest queue, based on the number of people already present. If a counter is empty, the person gets immediate billing, otherwise, they join the queue.
For every person, output the time when they finish billing and leave the counter.
Notes
- It takes 1 unit of time for the counter to process a person's bill.
- The counter processes the next person immediately after the current person leaves. Input/Output
- The first line contains
Ndenoting the number of counters. - The second line contains
Mdenoting the number of persons. - The third line contains an array
time, indicating the entry time of the people.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理