1199. Minimum Time to Build Blocks

leetcode hard

#array#backtracking#csharp#hard#heap#leetcode#queue

Task

Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.

Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.

Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.

Выведите минимальное время, необходимое для строительства всех блоков.

Изначально есть только один рабочий.

Пример:

Input: blocks = [1,2,3], split = 1

Output: 4

Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.

Then, use the two unassigned workers to build the first two blocks.

The cost is 1 + max(3, 1 + max(1, 2)) = 4.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int MinBuildTime(int[] blocks, int split) {
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        foreach (var block in blocks) {
            pq.Enqueue(block, block);
        }
        
        while (pq.Count > 1) {
            int x = pq.Dequeue();
            int y = pq.Dequeue();
            pq.Enqueue(split + y, split + y);
        }
        
        return pq.Dequeue();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinBuildTime(vector<int>& blocks, int split) {
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        foreach (var block in blocks) {
            pq.Enqueue(block, block);
        }
        
        while (pq.size() > 1) {
            int x = pq.Dequeue();
            int y = pq.Dequeue();
            pq.Enqueue(split + y, split + y);
        }
        
        return pq.Dequeue();
    }
}

Java solution

matched/original

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int block : blocks) {
            pq.offer(block);
        }

        while (pq.size() > 1) {
            int x = pq.poll();
            int y = pq.poll();
            pq.offer(split + y);
        }

        return pq.poll();
    }
}

Python solution

matched/original

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapq.heapify(blocks)
        
        while len(blocks) > 1:
            x = heapq.heappop(blocks)
            y = heapq.heappop(blocks)
            heapq.heappush(blocks, split + y)
        
        return heapq.heappop(blocks)

Go solution

matched/original

import (
    "container/heap"
)

func minBuildTime(blocks []int, split int) int {
    pq := &IntHeap{}
    heap.Init(pq)
    for _, block := range blocks {
        heap.Push(pq, block)
    }
    
    for pq.Len() > 1 {
        x := heap.Pop(pq).(int)
        y := heap.Pop(pq).(int)
        heap.Push(pq, split + y)
    }
    
    return heap.Pop(pq).(int)
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Explanation

Algorithm

Подготовка кучи строительного времени:

Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks.

Обработка кучи:

Пока в куче больше одного элемента:

- извлеките минимальное значение из кучи, обозначим его как x.

- извлеките следующее минимальное значение из кучи, обозначим его как y.

- создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу.

Возврат результата:

Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков.

😎