A robotic chemical delivery system for a college chemistry laboratory has been configured to work using only one type of glass flask per day. For each chemical ordered, it will be filled to a mark that is at least equal to the volume ordered. There are multiple flasks available, each with markings at various levels. Given a list of order requirements and a list of flasks with their measurements, determine the single type of flask that will result in minimal waste. Waste is the sum of marking - requirement for each order. Return the zero-based index of the flask type chosen. If there are multiple answers, return the minimum index. If no flask will satisfy the constraints, return -1. NOTE: The markings 2D array will be given in order of the flasks, i.e., the markings for the 0-index flask will be followed by markings of 1-index flask and so on. For each flask, the given markings will also be sorted in ascending order.
Constraints
An unknown secret for now
Example 1
Input:
requirements = [4, 6, 6, 7]
markings = [[0, 3], [0, 5], [0, 7], [1, 6], [1, 8], [1, 9], [2, 3], [2, 5], [2, 6]]Output:
0Explanation: The markings array is a 2D array where the first element is the flask number and the second an available marking. In this case, the first type has markings at 3, 5 and 7. The second type has them at 6, 8 and 9, and the third type has markings at 3, 5 and 6. Using the first flask type, the losses are 5-4=1, 7-6=1,7-6=1,7-7=0. 1+1+1+0=3 units wasted. Using the second flask type, losses are: 6-4 = 2, 6 - 6=0, 6-6=0, 8-7=1. 2+0 + 0 + 1 = 3 units wasted. The third flask type cannot be used because its maximum capacity is 6 and there is an order for 7. Two types of flasks can be used and 3 units will be lost. The lower index flask is at index 0.
解法
先按瓶子编号分组它们的刻度(已升序)。对每个瓶子用 bisect_left 二分找每个需求量对应的最小刻度，累计浪费值；若某个需求超过该瓶子最大刻度，跳过该瓶子。最后选浪费值最小且编号最小的瓶子。时间复杂度 O((M + F) log K)，M 是需求数，F 是总刻度数，K 是单瓶刻度数。
from typing import List
from bisect import bisect_left
def chooseFlask(requirements: List[int], markings: List[List[int]]) -> int:
flasks = {}
for f, m in markings:
flasks.setdefault(f, []).append(m)
best_idx, best_waste = -1, float('inf')
for idx in sorted(flasks.keys()):
marks = flasks[idx]
waste = 0
ok = True
for r in requirements:
i = bisect_left(marks, r)
if i == len(marks):
ok = False
break
waste += marks[i] - r
if ok and waste < best_waste:
best_waste = waste
best_idx = idx
return best_idxclass Solution {
int chooseFlask(int[] requirements, int[][] markings) {
TreeMap<Integer, List<Integer>> flasks = new TreeMap<>();
for (int[] m : markings) flasks.computeIfAbsent(m[0], k -> new ArrayList<>()).add(m[1]);
int bestIdx = -1;
long bestWaste = Long.MAX_VALUE;
for (Map.Entry<Integer, List<Integer>> e : flasks.entrySet()) {
List<Integer> marks = e.getValue();
long waste = 0;
boolean ok = true;
for (int r : requirements) {
int lo = 0, hi = marks.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (marks.get(mid) < r) lo = mid + 1; else hi = mid;
}
if (lo == marks.size()) { ok = false; break; }
waste += marks.get(lo) - r;
}
if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = e.getKey(); }
}
return bestIdx;
}
}class Solution {
public:
int chooseFlask(vector<int>& requirements, vector<vector<int>>& markings) {
map<int, vector<int>> flasks;
for (auto& m : markings) flasks[m[0]].push_back(m[1]);
int bestIdx = -1;
long long bestWaste = LLONG_MAX;
for (auto& [idx, marks] : flasks) {
long long waste = 0;
bool ok = true;
for (int r : requirements) {
auto it = lower_bound(marks.begin(), marks.end(), r);
if (it == marks.end()) { ok = false; break; }
waste += *it - r;
}
if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = idx; }
}
return bestIdx;
}
};