Problem

You are given an integer array timeReq and an integer splitTime.

In the microscopic world of the human body, the immune system faces an extraordinary challenge: combatting a rapidly multiplying bacterial colony that threatens the body’s survival.

Initially, only one white blood cell (WBC) is deployed to eliminate the bacteria. However, the lone WBC quickly realizes it cannot keep up with the bacterial growth rate.

The WBC devises a clever strategy to fight the bacteria:

  • The ith bacterial strain takes timeReq[i] units of time to be eliminated.
  • A single WBC can eliminate only one bacterial strain. Afterwards, the WBC is exhausted and cannot perform any other tasks.
  • A WBC can split itself into two WBCs, but this requires splitTime units of time. Once split, the two WBCs can work in parallel on eliminating the bacteria.
  • Only one WBC can work on a single bacterial strain. Multiple WBCs cannot attack one strain in parallel.

You must determine the minimum time required to eliminate all the bacterial strains.

Note that the bacterial strains can be eliminated in any order.

Examples

Example 1

Example 2

Solution

Method 1 – Greedy + Min-Heap (Priority Queue)

Intuition

To minimize the total time, we want to split WBCs as efficiently as possible so that the largest timeReq values are processed in parallel. This is similar to the optimal task scheduling problem, where we always split until we have enough WBCs to process all strains, then assign the largest tasks to separate WBCs.

Approach

  1. Sort timeReq in descending order.
  2. Use a min-heap to simulate available WBCs (each with a ready time).
  3. Start with one WBC at time 0.
  4. For each strain (from largest to smallest timeReq):
    • Pop the earliest available WBC (with the smallest ready time).
    • The WBC can either split (if more WBCs are needed) or process the strain.
    • If splitting, push two WBCs with ready time = current ready time + splitTime.
    • If processing, push the finish time = current ready time + timeReq[i].
  5. Continue until all strains are assigned.
  6. The answer is the maximum finish time among all WBCs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minTimeToEliminateBacteria(vector<int>& timeReq, int splitTime) {
        priority_queue<int, vector<int>, greater<int>> pq;
        int n = timeReq.size();
        sort(timeReq.rbegin(), timeReq.rend());
        pq.push(0);
        for (int t : timeReq) {
            int ready = pq.top(); pq.pop();
            pq.push(ready + t);
            if (pq.size() < n) {
                pq.push(ready + splitTime);
            }
        }
        int ans = 0;
        while (!pq.empty()) {
            ans = max(ans, pq.top());
            pq.pop();
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import "container/heap"

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any          { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

func minTimeToEliminateBacteria(timeReq []int, splitTime int) int {
    n := len(timeReq)
    sort.Sort(sort.Reverse(sort.IntSlice(timeReq)))
    h := &IntHeap{0}
    heap.Init(h)
    for _, t := range timeReq {
        ready := heap.Pop(h).(int)
        heap.Push(h, ready+t)
        if h.Len() < n {
            heap.Push(h, ready+splitTime)
        }
    }
    ans := 0
    for h.Len() > 0 {
        if (*h)[0] > ans { ans = (*h)[0] }
        heap.Pop(h)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minTimeToEliminateBacteria(int[] timeReq, int splitTime) {
        int n = timeReq.length;
        Arrays.sort(timeReq);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = n - 1; i >= 0; --i) pq.offer(timeReq[i]);
        Queue<Integer> wbc = new PriorityQueue<>();
        wbc.offer(0);
        for (int i = 0; i < n; ++i) {
            int ready = wbc.poll();
            wbc.offer(ready + pq.poll());
            if (wbc.size() < n) wbc.offer(ready + splitTime);
        }
        int ans = 0;
        while (!wbc.isEmpty()) ans = Math.max(ans, wbc.poll());
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minTimeToEliminateBacteria(timeReq: IntArray, splitTime: Int): Int {
        val n = timeReq.size
        timeReq.sortDescending()
        val pq = java.util.PriorityQueue<Int>()
        pq.add(0)
        for (t in timeReq) {
            val ready = pq.poll()
            pq.add(ready + t)
            if (pq.size < n) pq.add(ready + splitTime)
        }
        var ans = 0
        while (pq.isNotEmpty()) ans = maxOf(ans, pq.poll())
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import heapq
class Solution:
    def minTimeToEliminateBacteria(self, timeReq: list[int], splitTime: int) -> int:
        n = len(timeReq)
        timeReq.sort(reverse=True)
        pq = [0]
        for t in timeReq:
            ready = heapq.heappop(pq)
            heapq.heappush(pq, ready + t)
            if len(pq) < n:
                heapq.heappush(pq, ready + splitTime)
        return max(pq)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn min_time_to_eliminate_bacteria(time_req: Vec<i32>, split_time: i32) -> i32 {
        let n = time_req.len();
        let mut time_req = time_req;
        time_req.sort_by(|a, b| b.cmp(a));
        let mut pq = std::collections::BinaryHeap::new();
        pq.push(Reverse(0));
        for &t in &time_req {
            let Reverse(ready) = pq.pop().unwrap();
            pq.push(Reverse(ready + t));
            if pq.len() < n {
                pq.push(Reverse(ready + split_time));
            }
        }
        pq.into_iter().map(|Reverse(x)| x).max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minTimeToEliminateBacteria(timeReq: number[], splitTime: number): number {
        const n = timeReq.length;
        timeReq.sort((a, b) => b - a);
        const pq: number[] = [0];
        for (const t of timeReq) {
            pq.sort((a, b) => a - b);
            const ready = pq.shift()!;
            pq.push(ready + t);
            if (pq.length < n) pq.push(ready + splitTime);
        }
        return Math.max(...pq);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting and heap operations for n strains.
  • 🧺 Space complexity: O(n) — For the heap.