前往
大廳
主題

[leetcode]1889. Minimum Space Wasted From Packaging

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-31 12:00:05 | 巴幣 2 | 人氣 330

題目: 1889. Minimum Space Wasted From Packaging
難度: Hard
目前下列解法的時間複雜度: O( |包裹|*lg(|包裹|) + |所有箱子|*lg(max(|所有箱子|,|包裹|)) )


題目說明

給定一堆包裹及一堆箱子供應商。每個包裹有一個大小;每個箱子有一個容量。
選擇一個箱子供應商(供應多種箱子,每種箱子無限供應),每個包裹使用一個箱子裝箱,用此供應商的箱子裝完所有包裹,計算最少空間浪費(=箱子容量-包裹大小)總和。
問所有箱子供應商中,可以達成的最小浪費為何。若沒有任何一個箱子供應商可以提供夠大的箱子裝下最大的包裹,則回傳 -1 。


解法: just do it

1. 把包裹排序,並建立包裹 prefix sum 。
2. 分別對每個箱子供應商的箱子排序
3. 從小箱子到大箱子,每個箱子花 O(lg(|包裹|) 的時間取得浪費的空間。
4. 選最小浪費%1000000007後回傳。
5. 該 long long 的記得 long long 。


source code

創作回應

相關創作

更多創作