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].
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B, F) {
if (F > (A.length/2)) {
return solution(B, A, B.length-F);
}
if (F === 0) {
return B.reduce((total, current) => total + current);
}
if (F === A.length) {
return A.reduce((total, current) => total + current);
}
let tradeOffs = tradeOff(A, B);
let trades = mostAdvantageous(tradeOffs, F)
let count = 0;
for (let i = 0; i < A.length; i++) {
if (trades[i]) {
count += A[i];
} else {
count += B[i];
}
}
return count;
}
function tradeOff(A, B) {
let tradeOffs = [];
for (let i = 0; i < A.length; i++) {
tradeOffs[i] = A[i] - B[i];
}
return tradeOffs;
}
class Heap {
constructor() {
this.storage = [0];
this.size = 0;
}
insert(obj) {
this.storage.push(obj);
this.size += 1;
this._bubble_up(this.size);
}
delete() {
let prevHead = this.storage[1];
this.storage[1] = this.storage[this.size];
this.size -= 1;
this.storage.pop();
this._sift_down(1);
return prevHead;
}
get_max() {
return this.storage[1];
}
get_size() {
return this.size;
}
_bubble_up(index) {
while (Math.floor(index / 2) > 0) {
if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
[ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
} else {
break;
}
index = Math.floor(index / 2);
}
}
_sift_down(index) {
while ((index * 2) <= this.size) {
let max_child = this._max_child(index);
if (this.storage[index].value < this.storage[max_child].value) {
[ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
} else {
break;
}
index = max_child;
}
}
_max_child(index) {
if (index * 2 + 1 > this.size) {
return index * 2;
} else {
if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
return index * 2;
} else {
return index * 2 + 1;
}
}
}
}
function mostAdvantageous(tradeOffs, F) {
let max = new Heap();
for (let i = 0; i < tradeOffs.length; i++) {
let current = { index: i, value: tradeOffs[i] }
max.insert(current);
}
let returnedMax = {};
let i = 0;
while (i < F) {
returnedMax[max.get_max().index] = max.get_max().value;
max.delete();
i++;
}
return returnedMax;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B, F) {
if (F > (A.length/2)) {
return solution(B, A, B.length-F);
}
if (F === 0) {
return B.reduce((total, current) => total + current);
}
if (F === A.length) {
return A.reduce((total, current) => total + current);
}
let tradeOffs = tradeOff(A, B);
let trades = mostAdvantageous(tradeOffs, F)
let count = 0;
for (let i = 0; i < A.length; i++) {
if (trades[i]) {
count += A[i];
} else {
count += B[i];
}
}
return count;
}
function tradeOff(A, B) {
let tradeOffs = [];
for (let i = 0; i < A.length; i++) {
tradeOffs[i] = A[i] - B[i];
}
return tradeOffs;
}
class Heap {
constructor() {
this.storage = [0];
this.size = 0;
}
insert(obj) {
this.storage.push(obj);
this.size += 1;
this._bubble_up(this.size);
}
delete() {
let prevHead = this.storage[1];
this.storage[1] = this.storage[this.size];
this.size -= 1;
this.storage.pop();
this._sift_down(1);
return prevHead;
}
get_max() {
return this.storage[1];
}
get_size() {
return this.size;
}
_bubble_up(index) {
while (Math.floor(index / 2) > 0) {
if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
[ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
} else {
break;
}
index = Math.floor(index / 2);
}
}
_sift_down(index) {
while ((index * 2) <= this.size) {
let max_child = this._max_child(index);
if (this.storage[index].value < this.storage[max_child].value) {
[ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
} else {
break;
}
index = max_child;
}
}
_max_child(index) {
if (index * 2 + 1 > this.size) {
return index * 2;
} else {
if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
return index * 2;
} else {
return index * 2 + 1;
}
}
}
}
function mostAdvantageous(tradeOffs, F) {
let max = new Heap();
for (let i = 0; i < tradeOffs.length; i++) {
let current = { index: i, value: tradeOffs[i] }
max.insert(current);
}
let returnedMax = {};
let i = 0;
while (i < F) {
returnedMax[max.get_max().index] = max.get_max().value;
max.delete();
i++;
}
return returnedMax;
}[[3, 2, 1], [5, 2, 1], 0]
[[3, 2, 1], [5, 2, 1], 1]
[[3, 2, 1], [5, 2, 1], 3]
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B, F) {
if (F > (A.length/2)) {
return solution(B, A, B.length-F);
}
if (F === 0) {
return B.reduce((total, current) => total + current);
}
if (F === A.length) {
return A.reduce((total, current) => total + current);
}
let tradeOffs = tradeOff(A, B);
let trades = mostAdvantageous(tradeOffs, F)
let count = 0;
for (let i = 0; i < A.length; i++) {
if (trades[i]) {
count += A[i];
} else {
count += B[i];
}
}
return count;
}
function tradeOff(A, B) {
let tradeOffs = [];
for (let i = 0; i < A.length; i++) {
tradeOffs[i] = A[i] - B[i];
}
return tradeOffs;
}
class Heap {
constructor() {
this.storage = [0];
this.size = 0;
}
insert(obj) {
this.storage.push(obj);
this.size += 1;
this._bubble_up(this.size);
}
delete() {
let prevHead = this.storage[1];
this.storage[1] = this.storage[this.size];
this.size -= 1;
this.storage.pop();
this._sift_down(1);
return prevHead;
}
get_max() {
return this.storage[1];
}
get_size() {
return this.size;
}
_bubble_up(index) {
while (Math.floor(index / 2) > 0) {
if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
[ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
} else {
break;
}
index = Math.floor(index / 2);
}
}
_sift_down(index) {
while ((index * 2) <= this.size) {
let max_child = this._max_child(index);
if (this.storage[index].value < this.storage[max_child].value) {
[ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
} else {
break;
}
index = max_child;
}
}
_max_child(index) {
if (index * 2 + 1 > this.size) {
return index * 2;
} else {
if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
return index * 2;
} else {
return index * 2 + 1;
}
}
}
}
function mostAdvantageous(tradeOffs, F) {
let max = new Heap();
for (let i = 0; i < tradeOffs.length; i++) {
let current = { index: i, value: tradeOffs[i] }
max.insert(current);
}
let returnedMax = {};
let i = 0;
while (i < F) {
returnedMax[max.get_max().index] = max.get_max().value;
max.delete();
i++;
}
return returnedMax;
}[[3, 2, 1], [5, 2, 1], 0]
[[3, 2, 1], [5, 2, 1], 1]
[[3, 2, 1], [5, 2, 1], 3]
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B, F) {
if (F > (A.length/2)) {
return solution(B, A, B.length-F);
}
if (F === 0) {
return B.reduce((total, current) => total + current);
}
if (F === A.length) {
return A.reduce((total, current) => total + current);
}
let tradeOffs = tradeOff(A, B);
let trades = mostAdvantageous(tradeOffs, F)
let count = 0;
for (let i = 0; i < A.length; i++) {
if (trades[i]) {
count += A[i];
} else {
count += B[i];
}
}
return count;
}
function tradeOff(A, B) {
let tradeOffs = [];
for (let i = 0; i < A.length; i++) {
tradeOffs[i] = A[i] - B[i];
}
return tradeOffs;
}
class Heap {
constructor() {
this.storage = [0];
this.size = 0;
}
insert(obj) {
this.storage.push(obj);
this.size += 1;
this._bubble_up(this.size);
}
delete() {
let prevHead = this.storage[1];
this.storage[1] = this.storage[this.size];
this.size -= 1;
this.storage.pop();
this._sift_down(1);
return prevHead;
}
get_max() {
return this.storage[1];
}
get_size() {
return this.size;
}
_bubble_up(index) {
while (Math.floor(index / 2) > 0) {
if (this.storage[Math.floor(index / 2)].value < this.storage[index].value) {
[ this.storage[Math.floor(index / 2)], this.storage[index] ] = [ this.storage[index], this.storage[Math.floor(index / 2)] ];
} else {
break;
}
index = Math.floor(index / 2);
}
}
_sift_down(index) {
while ((index * 2) <= this.size) {
let max_child = this._max_child(index);
if (this.storage[index].value < this.storage[max_child].value) {
[ this.storage[index], this.storage[max_child] ] = [ this.storage[max_child], this.storage[index] ];
} else {
break;
}
index = max_child;
}
}
_max_child(index) {
if (index * 2 + 1 > this.size) {
return index * 2;
} else {
if (this.storage[index * 2].value > this.storage[index * 2 + 1].value) {
return index * 2;
} else {
return index * 2 + 1;
}
}
}
}
function mostAdvantageous(tradeOffs, F) {
let max = new Heap();
for (let i = 0; i < tradeOffs.length; i++) {
let current = { index: i, value: tradeOffs[i] }
max.insert(current);
}
let returnedMax = {};
let i = 0;
while (i < F) {
returnedMax[max.get_max().index] = max.get_max().value;
max.delete();
i++;
}
return returnedMax;
}The solution obtained perfect score.