hardHeap and Priority QueuePattern: Heap Operations
Minimize Equipment Collection Trips Solution
Problem Statement
You are given an array of pairs of integers, where each pair represents the weight and priority of an equipment. Determine the order in which the equipment should be collected to minimize the number of trips, given a capacity constraint.
Examples
Example 1:
Input:[[3, 1], [2, 2], [1, 3]], 4
Output:undefined
Explanation: Collect equipment with priority 3 first, then collect the remaining equipment.
Example 2:
Input:[[1, 1], [1, 1], [1, 1]], 2
Output:undefined
Explanation: Collect two equipment in the first trip and the remaining one in the second trip.
Constraints
- 1 <= equipment.length <= 10^5
- 1 <= weight, priority <= 10^5
- 1 <= capacity <= 10^5
Time: O(N log N) Space: O(N)
The optimal approach involves a greedy strategy. First, sort all equipment in descending order of their priority. Then, use a min-priority queue to manage the remaining capacities of all active trips. Iterate through the priority-sorted equipment: for each item, attempt to place it into an existing trip that has the smallest remaining capacity but can still accommodate the item. If no such trip exists, a new trip is started. This ensures critical items are processed first and existing trips are utilized efficiently.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
import heapq
def main():
n = int(sys.stdin.readline())
equipment = []
for _ in range(n):
weight, priority = map(int, sys.stdin.readline().split())
equipment.append((weight, priority))
capacity = int(sys.stdin.readline())
equipment.sort(key=lambda x: x[1], reverse=True)
trips = 0
curr_capacity = 0
for weight, _ in equipment:
if curr_capacity + weight > capacity:
trips += 1
curr_capacity = 0
curr_capacity += weight
if curr_capacity > 0: trips += 1
print(trips)
if __name__ == "__main__":
main()