ErdemT09
commented
3 years ago There are also few binary searching solutions I don't really get: https://nagato1208.github.io/2019/09/21/leetcode-1199-Minimum-Time-to-Build-Blocks/
class Solution(object):
def minBuildTime(self, blocks, split):
"""
:type blocks: List[int]
:type split: int
:rtype: int
"""
blocks.sort(reverse=True)
p=1
q=split*10+10**5
def check(time,num,arr):
if arr and time<=0:
return False
if not arr:
return True
if arr[0]>time:
return False
if num>=len(arr) and arr[0]<=time:
return True
index=0
while index<len(arr) and arr[index]+split>time:
index+=1
if index>=num:
return False
return check(time-split,(num-index)*2,arr[index:])
while p<q:
mid=(p+q)/2
if check(mid,1,blocks):
q=mid
else:
p=mid+1
return pfunc minBuildTime(blocks []int, split int) int {
Search := func(blocks []int, split int, time int) bool {
workers := 1
for i := len(blocks) - 1; i >= 0; i-- {
if blocks[i] > time || workers == 0 {
return false
}
for blocks[i] + split <= time {
workers *= 2
if workers >= len(blocks) {
return true
}
time -= split
}
workers--
}
return true
}
low, high := 0, 100000007
ans := 0
sort.Ints(blocks)
for low <= high {
mid := (low + high) / 2
if Search(blocks, split, mid) {
ans = mid
high = mid - 1
} else {
low = mid + 1
}
}
return ans
}class Solution {
public:
int minBuildTime(vector<int>& blocks, int split) {
int n = blocks.size();
auto check = [&](int m)
{
vector<int> v;
for (auto x : blocks)
{
int len = (m-x)/split;
v.push_back(len);
}
sort(v.begin(), v.end());
int tot = 0;
int cur = 1;
int i = 0;
while (i < n)
{
if (v[i] == tot)
{
if (cur == 0) return 0;
-- cur;
i ++;
}
else
{
cur = cur*2;
tot ++;
if (cur > 1000) return 1;
}
}
return 1;
};
int L = *max_element(blocks.begin(), blocks.end()), R = 1000000;
/*
printf("%d %d\n", L, R);
printf("%d\n", check(5));
for (int i = 1; i <= 10; ++ i)
printf("%d", check(i));
return -1;
*/
int ret = R;
while (L <= R)
{
int m = (L+R)/2;
if (check(m))
{
ret = m;
R = m-1;
}
else
L = m+1;
}
return ret;
}
};class Solution {
public:
int minBuildTime(vector<int>& blocks, int split) {
sort(blocks.rbegin(), blocks.rend());
int l = 0;
int r = 1e9 + 7;
int ans = -1;
while (l <= r) {
int m = (l + r) / 2;
if (bs(blocks, split, m)) {
ans = m;
r = m - 1;
}
else l = m + 1;
}
return ans;
}
bool bs(vector<int>& blocks, int split, int time) {
int workers = 1;
for (int i = 0; i < blocks.size(); i++) {
if (!workers || blocks[i] > time)
return false;
while (blocks[i] + split <= time) {
workers *= 2;
if (workers > blocks.size())
return true;
time -= split;
}
workers--;
}
return true;
}
}; public int minBuildTime(int[] blocks, int split) {
// A worker can either split into two workers or build a block and go home
int n = blocks.length;
Arrays.sort(blocks);
int maxVal = blocks[n - 1];
// Binary search the maximum time in the obvious range of [max, 10*split +
// maxv].
int lo = maxVal;
int hi = split * 10 + maxVal;
int ans = hi;
while (lo < hi) {
int target = (lo + hi) / 2;
if (isOk(target, blocks, split)) {
ans = Math.min(ans, target);
hi = target;
} else {
lo = target + 1;
}
}
return ans;
}
// Check whether all blocks can be built in time t.
private boolean isOk(int t, int[] blocks, int split) {
// current level and corresponding number of workers
int level = 0;
int worker = 1;
for (int i = blocks.length - 1; i >= 0; i--) {
// maximal number of split before the worker build the block
// value of k is non-descending when i increase.
int k = (t - blocks[i]) / split;
while (level < k) {
worker *= 2;
level++;
// avoid overflow
if (worker > i) {
return true;
}
}
if (--worker < 0) {
return false;
}
}
return true;
}
Resolves: #235
Algorithm
If we have some group of blocks, we would get the minimum by first picking two smallest blocks, and creating a worker for them. The result for these would be then the larger cost + worker cost. If we have third block, we would calculate the total cost by comparing the cost of the two and this block's. The minimum can be get by the procedure: Split the first worker. Split one of the workers and build the large block. Then build the two small blocks. Which gives the total:
split + max(third, split + max(first, second))Here,
split+max(first,second)can be treated as an entity, a cost itself. Then each time, we should pick the two smallest entities, add the split cost to them, and add it back to the list of entities, which is initially just the blocks.This corresponds to a Huffman tree, where connecting two nodes needs an extra cost:
With the method above, we basically pick the shortest distance in a Huffman tree with connection weights. But we don't need to directly find the shortest path as we can implement it with a priority queue while building the tree.