__Love_Rain__
Senior Member
Hi các bác, mình có implement theo cách bên dưới, fail test case cuối nhưng đang chưa tìm ra là vấn đề sai nằm ở đâu. Mình nhờ mọi người check hộ ạ. Cảm ơn mọi người!
- Về mặt ý tưởng mình sẽ sort difficulty, sau đó check nếu có difficulty lớn nhưng profit nhỏ hơn sẽ ignore. Sau cùng binary search để tìm profit phù hợp nhất.
- Về mặt ý tưởng mình sẽ sort difficulty, sau đó check nếu có difficulty lớn nhưng profit nhỏ hơn sẽ ignore. Sau cùng binary search để tìm profit phù hợp nhất.
JavaScript:
/**
* @param {number[]} difficulty
* @param {number[]} profit
* @param {number[]} worker
* @return {number}
*/
var maxProfitAssignment = function (difficulty, profit, worker) {
let curMax = 0;
let m = {};
for (let i = 0; i < difficulty.length; i++) {
m[difficulty[i]] = profit[i];
}
const sortedDif = difficulty.sort((a, b) => a - b);
const t = [];
for (let i = 0; i < sortedDif.length; i++) {
if (m[sortedDif[i]] > curMax) {
curMax = m[sortedDif[i]]
t.push(sortedDif[i])
} else {
continue;
}
}
function binarySearchMaxLE(dif, num) {
let low = 0, high = dif.length - 1;
let result = null;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (dif[mid] <= num) {
result = dif[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
let r = 0;
for (const w of worker) {
const p = binarySearchMaxLE(t, w);
r += p ? m[p] : 0;
}
return r;
};