-
Notifications
You must be signed in to change notification settings - Fork 0
/
lesson14.js
94 lines (75 loc) · 2.11 KB
/
lesson14.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
//nails blank
function solution(A, B, C) {
var arrays = []
var nailed = {}
A.map(function(value, index) {
var newArray = []
for (i = A[index]; i <= B[index]; i++) {
newArray.push(i)
}
arrays.push(newArray)
})
for (j = 0;j < C.length; j++) {
arrays.map(function(plank, index) {
if (plank.indexOf(C[j]) > -1) {
nailed[index] = true
}
})
if (Object.keys(nailed).length === arrays.length) return j + 1
}
return -1
}
//nail 2
function solution(A, B, C) {
var arrays = []
var nailed = {}
A.map(function(value, index) {
var newArray = []
for (i = A[index]; i <= B[index]; i++) {
newArray.push(i)
}
arrays.push(newArray)
})
for (j = 0;j < C.length; j++) {
for (x = 0; x < arrays.length; x++) {
if (arrays[x].indexOf(C[j]) > -1) {
nailed[x] = true
if (Object.keys(nailed).length === arrays.length) return j + 1
}
}
}
return -1
}
//minMaxDivision
function solution(maxNumBlocks, M, array) {
var lowerSum = Math.max.apply(null, array) //pega o maior elemento do array
var upperSum = array.reduce((a, c) => a + c, 0) //soma todo array
var result = -1
while (lowerSum <= upperSum) {
var tentativeSum = Math.floor((lowerSum + upperSum) / 2) //binary search, soma maior e menor e divide por dois
if (tentativeSumIsPossible(array, maxNumBlocks, tentativeSum)) {
result = tentativeSum
upperSum = tentativeSum - 1
} else {
lowerSum = tentativeSum + 1
}
}
return result
}
//check if it has a valid block with the tentative
function tentativeSumIsPossible(array, maxNumBlocks, tentativeSum) {
var curBlockSum = 0
var numBlocks = 1
for (let elem of array) {
//se ainda cabe aumenta o currentblock
if (curBlockSum + elem <= tentativeSum) {
curBlockSum += elem
//se não cria outro block
} else {
numBlocks++
curBlockSum = elem
}
if (numBlocks > maxNumBlocks) return false
}
return true
}