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.
解法
每个柜台维护一个「下一次可服务的时间戳」。按 time 顺序处理每个人：选 next_free 最小的柜台(最小堆)，若 next_free ≤ arrival，则该人立刻被服务，结束时间 = arrival + 1；否则要等，结束时间 = next_free + 1。更新堆即可。注意人按到达时间排序输出对应结束时间。时间 O(M log N)，空间 O(N)。
import heapq
from typing import List
def shoppingAndBilling(N: int, M: int, time: List[int]) -> List[int]:
# min-heap of (next_free_time, counter_id)
heap: list[tuple[int, int]] = [(0, i) for i in range(N)]
heapq.heapify(heap)
res: List[int] = []
for arrival in time:
free, cid = heapq.heappop(heap)
start = max(free, arrival)
finish = start + 1
res.append(finish)
heapq.heappush(heap, (finish, cid))
return resimport java.util.*;
class Solution {
int[] shoppingAndBilling(int N, int M, int[] time) {
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) ->
a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
for (int i = 0; i < N; i++) heap.offer(new long[]{0, i});
int[] res = new int[M];
for (int i = 0; i < M; i++) {
long[] top = heap.poll();
long start = Math.max(top[0], time[i]);
long finish = start + 1;
res[i] = (int) finish;
heap.offer(new long[]{finish, top[1]});
}
return res;
}
}#include <vector>
#include <queue>
#include <algorithm>
class Solution {
public:
std::vector<int> shoppingAndBilling(int N, int M, std::vector<int>& time) {
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<>> heap;
for (int i = 0; i < N; i++) heap.push({0, i});
std::vector<int> res;
for (int i = 0; i < M; i++) {
auto [free, cid] = heap.top(); heap.pop();
long long start = std::max(free, (long long) time[i]);
long long finish = start + 1;
res.push_back((int) finish);
heap.push({finish, cid});
}
return res;
}
};