Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.
Task description
A company has employed N developers (numbered from 0 to N−1) and wants to divide them into two teams. The first is a front-end team with F developers. The second is a back-end team with N−F developers. If the K-th developer is assigned to the front-end team then their contribution is A[K], and if they are assigned to the back-end team then their contribution is B[K]. What is the maximum sum of contributions the company can achieve?
Write a function:
function solution(A, B, F);
that, given two arrays A, B (consisting of N integers each) and the integer F, returns the maximum sum of contributions the company can achieve.
Examples:
1. Given A = [4, 2, 1], B = [2, 5, 3] and F = 2, the function should return 10. There should be two front-end developers and one back-end developer. The 0th and 2nd developers should be assigned to the front-end team (with contributions 4 and 1) and the 1st developer should be assigned to the back-end team (with contribution 5).
2. Given A = [7, 1, 4, 4], B = [5, 3, 4, 3] and F = 2, the function should return 18. The 0th and 3rd developers should be assigned to the front-end team and the 1st and 2nd developers should be assigned to the back-end team.
3. Given A = [5, 5, 5], B = [5, 5, 5] and F = 1, the function should return 15. The 0th developer can be assigned to the front-end team and the 1st and 2nd developers can be assigned to the back-end team.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..200,000];
- arrays A and B have equal lengths;
- each element of array A is an integer within the range [0..1,000];
- F is an integer within the range [0..N].
Task timeline
const solution = (a, b, f) => {
const diff = a.map((value, index) => ({
a: value,
b: b[index],
i: index,
diff: value - b[index],
}));
diff.sort((el1, el2) => el2.diff - el1.diff);
const contribA = diff.slice(0, f);
const contribB = diff.slice(f, a.length);
const sumA = contribA.reduce((sum, item) => sum + item.a, 0);
const sumB = contribB.reduce((sum, item) => sum + item.b, 0);
return sumA + sumB;
};const solution = (a, b, f) => {
const diff = a.map((value, index) => ({
a: value,
b: b[index],
i: index,
diff: value - b[index],
}));
diff.sort((el1, el2) => el2.diff - el1.diff);
const contribA = diff.slice(0, f);
const contribB = diff.slice(f, a.length);
const sumA = contribA.reduce((sum, item) => sum + item.a, 0);
const sumB = contribB.reduce((sum, item) => sum + item.b, 0);
return sumA + sumB;
};const solution = (a, b, f) => {
const diff = a.map((value, index) => ({
a: value,
b: b[index],
i: index,
diff: value - b[index],
}));
diff.sort((el1, el2) => el2.diff - el1.diff);
const contribA = diff.slice(0, f);
const contribB = diff.slice(f, a.length);
const sumA = contribA.reduce((sum, item) => sum + item.a, 0);
const sumB = contribB.reduce((sum, item) => sum + item.b, 0);
return sumA + sumB;
};The solution obtained perfect score.
N = 20. Some developers have small difference between A[i] and B[i].
N = 300. Some developers have small difference between A[i] and B[i].
N = 200,000. Some developers have small difference between A[i] and B[i].