LeetCode Entry

2279. Maximum Bags With Full Capacity of Rocks

27.12.2022 medium 2022 kotlin

fun maximumBags(capacity: IntArray, rocks: IntArray, additionalRocks: Int): Int {

2279. Maximum Bags With Full Capacity of Rocks medium

https://t.me/leetcode_daily_unstoppable/65

blog post

    fun maximumBags(capacity: IntArray, rocks: IntArray, additionalRocks: Int): Int {
       val inds = Array<Int>(capacity.size) { it }
       inds.sortWith(Comparator { a,b -> capacity[a]-rocks[a] - capacity[b] + rocks[b] })
       var rocksRemain = additionalRocks
       var countFull = 0
       for (i in 0..inds.lastIndex) {
           val toAdd = capacity[inds[i]] - rocks[inds[i]]
           if (toAdd > rocksRemain) break
           rocksRemain -= toAdd
           countFull++
       }
       return countFull
    }

We can logically deduce that the optimal solution is to take first bags with the smallest empty space. Make an array of indexes and sort it by difference between capacity and rocks. Then just simulate rocks addition to each bug from the smallest empty space to the largest.

Space: O(n), Time: O(nlogn)