Skip to content

3506. Find Time Required to Eliminate Bacterial Strains

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  long long minEliminationTime(vector<int>& timeReq, int splitTime) {
    priority_queue<long, vector<long>, greater<>> minHeap{timeReq.begin(),
                                                          timeReq.end()};
    minHeap.pop();

    while (true) {
      const long bacterial = splitTime + minHeap.top();
      minHeap.pop();
      if (minHeap.empty())
        return bacterial;
      if (bacterial > minHeap.top()) {
        minHeap.pop();
        minHeap.push(bacterial);
      }
    }

    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public long minEliminationTime(int[] timeReq, int splitTime) {
    PriorityQueue<Long> minHeap = new PriorityQueue<>();

    for (final long time : timeReq)
      minHeap.offer(time);

    minHeap.poll();

    while (true) {
      final long bacterial = splitTime + minHeap.peek();
      minHeap.poll();
      if (minHeap.isEmpty())
        return bacterial;
      if (bacterial > minHeap.peek()) {
        minHeap.poll();
        minHeap.offer(bacterial);
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def minEliminationTime(self, timeReq: list[int], splitTime: int) -> int:
    minHeap = timeReq.copy()
    heapq.heapify(minHeap)
    heapq.heappop(minHeap)

    while True:
      bacterial = splitTime + heapq.heappop(minHeap)
      if not minHeap:
        return bacterial
      heapq.heappushpop(minHeap, bacterial)