[Swift]LeetCode1199.建造街区的最短时间|MinimumTimeToBuildBlocks

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You are given a list of blocks, where blocks[i] = t means that the i-th block needs t units of time to be built. A block can only be built by exactly one worker.

A worker can either split into two workers (number of workers increases by one) or build a block then go home. Both decisions cost some time.

The time cost of spliting one worker into two workers is given as an integer split. Note that if two workers split at the same time, they split in parallel so the cost would be split.

Output the minimum time needed to build all blocks.

Initially, there is only one worker.

Example 1:

Input: blocks = 1
Output: 1
Explanation: We use 1 worker to build 1 block in 1 time unit.

Example 2:

Input: blocks = 5
Output: 7
Explanation: We split the worker into 2 workers in 5 time units then assign each of them to a block so the cost is 5 + max(1, 2) = 7.

Example 3:

Input: blocks = 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.

Note:

1 <= blocks.length <= 1000
1 <= blocks[i] <= 10^5
1 <= split <= 100

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有一个工人，请你最后输出建造完所有街区所需要的最少时间。

示例 1：

输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。

示例 2：

输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7

示例 3：

输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

提示：

1 <= blocks.length <= 1000
1 <= blocks[i] <= 10^5
1 <= split <= 100

优先队列

  1 class Solution {
  2     func minBuildTime(_ blocks: [Int], _ split: Int) -> Int {
  3         var pq = PriorityQueue<Int> { $0 < $1 }
  4         for v in blocks
  5         {
  6             pq.push(v)
  7         }
  8         while(pq.count >= 2)
  9         {
 10             let x:Int = pq.pop()!
 11             let y:Int = pq.pop()!
 12             pq.push(y + split)
 13         }
 14         return pq.pop() ?? 0
 15     }
 16 }
 17 
 18 public struct PriorityQueue<T> {
 19   fileprivate var heap: Heap<T>
 20   public init(sort: @escaping (T, T) -> Bool) {
 21     heap = Heap(sort: sort)
 22   }
 23 
 24   public var isEmpty: Bool {
 25     return heap.isEmpty
 26   }
 27 
 28   public var count: Int {
 29     return heap.count
 30   }
 31 
 32   public func peek() -> T? {
 33     return heap.peek()
 34   }
 35 
 36   public mutating func push(_ element: T) {
 37     heap.insert(element)
 38   }
 39 
 40   public mutating func pop() -> T? {
 41     return heap.remove()
 42   }
 43 
 44   public mutating func changePriority(index i: Int, value: T) {
 45     return heap.replace(index: i, value: value)
 46   }
 47 }
 48 
 49 extension PriorityQueue where T: Equatable {
 50   public func index(of element: T) -> Int? {
 51     return heap.index(of: element)
 52   }
 53 }
 54 
 55 public struct Heap<T> {
 56   var nodes = [T]()
 57 
 58   private var orderCriteria: (T, T) -> Bool
 59 
 60   public init(sort: @escaping (T, T) -> Bool) {
 61     self.orderCriteria = sort
 62   }
 63   
 64   public init(array: [T], sort: @escaping (T, T) -> Bool) {
 65     self.orderCriteria = sort
 66     configureHeap(from: array)
 67   }
 68 
 69   private mutating func configureHeap(from array: [T]) {
 70     nodes = array
 71     for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
 72       shiftDown(i)
 73     }
 74   }
 75   
 76   public var isEmpty: Bool {
 77     return nodes.isEmpty
 78   }
 79   
 80   public var count: Int {
 81     return nodes.count
 82   }
 83 
 84   @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
 85     return (i - 1) / 2
 86   }
 87 
 88   @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
 89     return 2*i + 1
 90   }
 91 
 92   @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
 93     return 2*i + 2
 94   }
 95   
 96   public func peek() -> T? {
 97     return nodes.first
 98   }
 99   
100   public mutating func insert(_ value: T) {
101     nodes.append(value)
102     shiftUp(nodes.count - 1)
103   }
104   
105   public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
106     for value in sequence {
107       insert(value)
108     }
109   }
110   
111   public mutating func replace(index i: Int, value: T) {
112     guard i < nodes.count else { return }
113     
114     remove(at: i)
115     insert(value)
116   }
117 
118   @discardableResult public mutating func remove() -> T? {
119     guard !nodes.isEmpty else { return nil }
120     
121     if nodes.count == 1 {
122       return nodes.removeLast()
123     } else {
124       let value = nodes[0]
125       nodes[0] = nodes.removeLast()
126       shiftDown(0)
127       return value
128     }
129   }
130   
131   @discardableResult public mutating func remove(at index: Int) -> T? {
132     guard index < nodes.count else { return nil }
133     
134     let size = nodes.count - 1
135     if index != size {
136       nodes.swapAt(index, size)
137       shiftDown(from: index, until: size)
138       shiftUp(index)
139     }
140     return nodes.removeLast()
141   }
142 
143   internal mutating func shiftUp(_ index: Int) {
144     var childIndex = index
145     let child = nodes[childIndex]
146     var parentIndex = self.parentIndex(ofIndex: childIndex)
147     
148     while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
149       nodes[childIndex] = nodes[parentIndex]
150       childIndex = parentIndex
151       parentIndex = self.parentIndex(ofIndex: childIndex)
152     }
153     
154     nodes[childIndex] = child
155   }
156 
157   internal mutating func shiftDown(from index: Int, until endIndex: Int) {
158     let leftChildIndex = self.leftChildIndex(ofIndex: index)
159     let rightChildIndex = leftChildIndex + 1
160 
161     var first = index
162     if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
163       first = leftChildIndex
164     }
165     if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
166       first = rightChildIndex
167     }
168     if first == index { return }
169     
170     nodes.swapAt(index, first)
171     shiftDown(from: first, until: endIndex)
172   }
173   
174   internal mutating func shiftDown(_ index: Int) {
175     shiftDown(from: index, until: nodes.count)
176   }
177   
178 }
179 
180 extension Heap where T: Equatable {
181     
182     public func index(of node: T) -> Int? {
183         return nodes.firstIndex(where: { $0 == node })
184     }
185     
186     @discardableResult public mutating func remove(node: T) -> T? {
187         if let index = index(of: node) {
188             return remove(at: index)
189         }
190         return nil
191     }
192 }