-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.js
180 lines (152 loc) · 5.03 KB
/
index.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
/**
* Example of Dynamic Programming.
* Related article on https://amcereijo.medium.com/real-dynamic-programming-example-with-javascript-666d54c6edf4
*/
/* Record<string, number>* */
const SERVICE_CPU_TIMES = {
two: 2,
seven: 7,
three: 3,
ten: 10,
five: 5,
one: 1,
six: 6,
eight: 8,
nine: 9,
four: 4,
};
/*
type Transaction = {
benefit: number,
service: string,
id: string,
};
type Element = {
totalBenefit: number,
totalCpuTime: number,
list: Transaction[],
};
*/
// min CPU time to be as the starting point
const MIN_CPU_TIME = Object.values(SERVICE_CPU_TIMES).reduce((min, cpuTime) => {
return cpuTime < min ? cpuTime : min
}, Number.MAX_SAFE_INTEGER);
/**
* Utility method for creating an "empty" Element, needed when no value exists for a position
* @returns {Element}
*/
function getDefaultEmptyElement() {
return { // Element
totalBenefit: 0,
totalCpuTime: 0,
list: []
};
}
/**
* Sorting the transactions
* @param {Transaction[]} transactions
* @returns
*/
function sortTransactions(transactions) {
return transactions.sort((t1, t2) => {
if (SERVICE_CPU_TIMES[t1.service] > SERVICE_CPU_TIMES[t2.service]) {
return 1;
}
if (SERVICE_CPU_TIMES[t1.service] < SERVICE_CPU_TIMES[t2.service]) {
return -1;
}
if (t1.benefit > t2.benefit) {
return 1;
}
if (t1.benefit < t2.benefit) {
return -1;
}
return 0;
})
}
/**
* Find a value in the previous row based in the actual one.
* @param {Element[][]} map
* @param {number} actualRow
* @param {number} column
* @returns {Element}
*/
function getPreviousRowElement(map, actualRow, column) {
return (map[actualRow - 1] && map[actualRow - 1][column]) || getDefaultEmptyElement()
}
/**
*
* @param {Element} element
* @param {Element} actualSelected
* @param {number} totalCpuTime
* @returns boolean
*/
function isMoreBenefitInEqualOrLessCpuTime(element, actualSelected, totalCpuTime) {
return element.totalBenefit >= actualSelected.totalBenefit && element.totalCpuTime <= totalCpuTime;
}
/**
*
* @param {Transaction[]} transactions
* @param {number} totalCpuTime
* @returns {Transaction[]}
*/
function getBestTransactions(transactions, totalCpuTime) {
if (!transactions.length || totalCpuTime < MIN_CPU_TIME) {
return [];
}
/* Element[][] */
const map = []; // the matrix where we will store the calculated values
/* Element */
let selectedElement; // the final selected element (the best one)
// we need to sort the transactions by cpu time asc (in case of same cpu time by benefits asc)
const sortedTransactions = sortTransactions(transactions);
console.log('sortedTransactions', sortedTransactions);
// iterate all over the transactions
for (let i = 0; i < sortedTransactions.length; i++) {
const actualTransaction = sortedTransactions[i];
const actualCpuTime = SERVICE_CPU_TIMES[actualTransaction.service];
map[i] = [];
// for each transaction we will calculate the value for each cpu time (from the lowest to the value recevied as max)
for (let j = MIN_CPU_TIME; j <= totalCpuTime; j++) {
/* Element */
let elementToAdd;
// the value for this cpu time (j) for the previous processed transaction(i)
const upRowElement = getPreviousRowElement(map, i, j);
// the value for this cpu time subtracking the cpu time for the actual transaction (j - cputime) for the previous processed transaction(i)
const upRowCpuTimeElement = getPreviousRowElement(map, i, j - actualCpuTime);
// the new total benefit (actual transaction + value in the previous row for the remainig cpu time)
const newTotalBenefit = actualTransaction.benefit + upRowCpuTimeElement.totalBenefit;
// has more benefit and ok with the availble cpu time?
if (upRowElement.totalBenefit > newTotalBenefit
|| (upRowCpuTimeElement.totalCpuTime + actualCpuTime > totalCpuTime)) {
elementToAdd = upRowElement;
} else {
elementToAdd = {
totalBenefit: newTotalBenefit,
totalCpuTime: upRowCpuTimeElement.totalCpuTime + actualCpuTime,
list: [...upRowCpuTimeElement.list, actualTransaction],
}
}
map[i][j] = elementToAdd;
// update the selected element when find other with more benefit
if(!selectedElement || isMoreBenefitInEqualOrLessCpuTime(elementToAdd, selectedElement, totalCpuTime)) {
selectedElement = elementToAdd;
}
}
}
console.log(selectedElement.totalBenefit, selectedElement.totalCpuTime)
return selectedElement.list || [];
}
const trans = [
{ id: 't3', benefit: 10, service: 'three' },
{ id: 't6', benefit: 4, service: 'three' },
{ id: 't9', benefit: 8, service: 'four' },
{ id: 't2', benefit: 10, service: 'five' },
{ id: 't5', benefit: 6, service: 'five' },
{ id: 't10', benefit: 3, service: 'five' },
{ id: 't1', benefit: 11, service: 'six' },
{ id: 't8', benefit: 5, service: 'seven' },
{ id: 't4', benefit: 15, service: 'eight' },
{ id: 't7', benefit: 11, service: 'eight' },
]
console.log(getBestTransactions(trans, 8));