DSA Master Logo
DSAMaster
Sign InSign Up
mediumHeapPattern: Heap

Timed Cost Element Manager Solution

Problem Statement

Implement a data structure, `TimedCostElementManager`, that efficiently manages elements, each characterized by a positive integer `deadline` and a positive integer `cost`. The data structure must support the following two operations: 1. `add(deadline, cost)`: Adds a new element with the given `deadline` and `cost` to the manager. 2. `process()`: Removes and returns the element that has the highest priority. The priority is determined first by the earliest `deadline`. If multiple elements share the same earliest `deadline`, then the element with the lowest `cost` has higher priority. If the manager is empty, `process()` should return `(-1, -1)`. Your implementation should ensure that both `add` and `process` operations are highly efficient.

Examples

Example 1:
Input:TimedCostElementManager manager = new TimedCostElementManager(); manager.add(5, 10); manager.add(2, 20); manager.add(5, 5); manager.process(); manager.add(1, 100); manager.process(); manager.process(); manager.process(); manager.process();
Output:(5, 5) (5, 10) (2, 20) (1, 100) (-1, -1)
Explanation: Elements are processed by earliest deadline. For elements with the same deadline (e.g., (5,10) and (5,5)), the one with the lowest cost is prioritized. The corrected output reflects this priority.
Example 2:
Input:TimedCostElementManager manager = new TimedCostElementManager(); manager.process(); manager.add(10, 50); manager.add(7, 30); manager.add(10, 20); manager.process(); manager.process(); manager.add(3, 15); manager.process(); manager.process();
Output:(-1, -1) (10, 20) (7, 30) (3, 15) (10, 50)
Explanation: Initially empty, `process()` returns `(-1, -1)`. Subsequent adds and processes follow the earliest deadline, then lowest cost priority. The corrected output reflects this priority.

Constraints

  • `1 <= deadline, cost <= 10^9`
  • `1 <= Total number of operations (add or process) <= 10^5`
  • Both `add` and `process` operations should have an average time complexity of `O(log N)`, where `N` is the number of elements currently in the manager.
  • The system should correctly handle duplicate `(deadline, cost)` pairs.
Time: O(log N) for both add and process operations, where N is the number of elements in the manager. Space: O(N) to store all elements in the heap.
The optimal approach uses a min-priority queue (min-heap). Each element `(deadline, cost)` is stored as a tuple or custom object. The heap is ordered such that elements with an earlier `deadline` have higher priority. If deadlines are equal, elements with a lower `cost` have higher priority. Both `add` (heappush) and `process` (heappop) operations will then take O(log N) time.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import heapq import sys class TimedCostElementManager: def __init__(self): # The heap will store tuples (deadline, cost). # Python's default tuple comparison works as desired: # It compares elements from left to right. # So (d1, c1) < (d2, c2) means d1 < d2, or d1 == d2 and c1 < c2. self.priority_queue = [] def add(self, deadline: int, cost: int) -> None: heapq.heappush(self.priority_queue, (deadline, cost)) def process(self) -> tuple[int, int]: if not self.priority_queue: return (-1, -1) return heapq.heappop(self.priority_queue) # Driver code def main(): manager = TimedCostElementManager() # Read the number of operations num_operations = int(sys.stdin.readline()) for _ in range(num_operations): line = sys.stdin.readline().split() command = line[0] if command == 'add': deadline = int(line[1]) cost = int(line[2]) manager.add(deadline, cost) elif command == 'process': result = manager.process() sys.stdout.write(f"{result[0]} {result[1]}\n") if __name__ == '__main__': main()

Related Problems

Implement Max Priority Queue
Heap•hard