Maximum Units on a Truck

🎯

Maximum Units on a Truck

easyGREEDYAmazonGoogle

Imagine you are a truck driver who needs to maximize the number of units loaded onto your truck from different box types, each with a limited number of boxes and units per box.

💡 This problem is a classic example of greedy algorithms where the goal is to make the locally optimal choice (pick boxes with the most units first) to achieve a globally optimal solution. Beginners often struggle because they try complex approaches instead of sorting and picking greedily.

📋

Problem Statement

You are assigned to put some number of boxes onto a truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]: - numberOfBoxes_i is the number of boxes of type i. - numberOfUnitsPerBox_i is the number of units in each box of the type i. You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. Return the maximum total number of units that can be put on the truck.

1 ≤ boxTypes.length ≤ 10^51 ≤ numberOfBoxes_i, numberOfUnitsPerBox_i ≤ 10^51 ≤ truckSize ≤ 10^9

💡

Example

Input"boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4"

Output8

Pick 1 box of type 0 (3 units) and 2 boxes of type 1 (2 units each) and 1 box of type 2 (1 unit). Total units = 3 + 4 + 1 = 8.

• truckSize is zero → output 0
• Only one box type with boxes less than truckSize → output all units from that type
• Multiple box types with same units per box → pick any order but total units same
• truckSize larger than total boxes available → output sum of all units

⚠️

Common Mistakes

Not sorting boxTypes by units per box descending

Leads to suboptimal total units and wrong answer

✅ Sort boxTypes by units per box in descending order before picking

Not stopping early when truckSize reaches zero

Unnecessary iterations wasting time

✅ Add a break condition when truckSize == 0

Using min(boxes, truckSize) incorrectly or off-by-one errors

May pick too many or too few boxes, causing wrong output

✅ Carefully use min to pick boxes without exceeding truckSize

Ignoring edge cases like truckSize = 0 or truckSize > total boxes

Code may crash or return incorrect results

✅ Handle these cases explicitly or ensure code logic covers them

🧠

Brute Force (Try All Combinations)

💡 This approach exists to understand the problem deeply by exploring all possible ways to pick boxes, even though it is inefficient. It helps beginners grasp the problem constraints and why greedy is better.

Intuition

Try every possible combination of boxes from all types to find the maximum units without exceeding truckSize.

Algorithm

1. Generate all subsets of box types with counts that do not exceed truckSize.
2. Calculate total units for each subset.
3. Track the maximum units found.
4. Return the maximum units after checking all subsets.

💡 This algorithm is hard to see because it involves exponential combinations and is not practical for large inputs, but it clarifies the problem's exhaustive nature.

</>

Code

from itertools import product

def maximumUnits(boxTypes, truckSize):
    max_units = 0
    n = len(boxTypes)
    # Generate all possible counts for each box type from 0 to min(boxes, truckSize)
    counts_ranges = [range(min(boxTypes[i][0], truckSize) + 1) for i in range(n)]
    for counts in product(*counts_ranges):
        total_boxes = sum(counts)
        if total_boxes <= truckSize:
            units = sum(counts[i] * boxTypes[i][1] for i in range(n))
            if units > max_units:
                max_units = units
    return max_units

# Example usage
if __name__ == '__main__':
    boxTypes = [[1,3],[2,2],[3,1]]
    truckSize = 4
    print(maximumUnits(boxTypes, truckSize))  # Output: 8

Line Notes

from itertools import productImport product to generate all combinations of box counts

counts_ranges = [range(min(boxTypes[i][0], truckSize) + 1) for i in range(n)]Create ranges for each box type from 0 to max boxes or truckSize to cover all possible counts

for counts in product(*counts_ranges):Iterate over all possible combinations of box counts across all box types

total_boxes = sum(counts)Calculate total boxes selected in current combination

if total_boxes <= truckSize:Only consider combinations that fit in the truck capacity

units = sum(counts[i] * boxTypes[i][1] for i in range(n))Calculate total units for current combination by multiplying counts with units per box

if units > max_units:Update max units if current combination yields more units

import java.util.*;

public class MaximumUnits {
    public static int maximumUnits(int[][] boxTypes, int truckSize) {
        int maxUnits = 0;
        int n = boxTypes.length;
        // Generate all combinations using recursion
        maxUnits = helper(boxTypes, truckSize, 0, new int[n]);
        return maxUnits;
    }

    private static int helper(int[][] boxTypes, int truckSize, int index, int[] counts) {
        if (index == boxTypes.length) {
            int totalBoxes = 0, totalUnits = 0;
            for (int i = 0; i < counts.length; i++) {
                totalBoxes += counts[i];
                if (totalBoxes > truckSize) return 0;
                totalUnits += counts[i] * boxTypes[i][1];
            }
            return totalUnits;
        }
        int maxUnits = 0;
        int maxCount = Math.min(boxTypes[index][0], truckSize);
        for (int c = 0; c <= maxCount; c++) {
            counts[index] = c;
            maxUnits = Math.max(maxUnits, helper(boxTypes, truckSize, index + 1, counts));
        }
        return maxUnits;
    }

    public static void main(String[] args) {
        int[][] boxTypes = {{1,3},{2,2},{3,1}};
        int truckSize = 4;
        System.out.println(maximumUnits(boxTypes, truckSize)); // Output: 8
    }
}

Line Notes

maxUnits = helper(boxTypes, truckSize, 0, new int[n]);Start recursive exploration of all box count combinations from index 0

if (index == boxTypes.length)Base case: all box types have been considered

for (int c = 0; c <= maxCount; c++)Try all counts from 0 to max boxes for current box type

if (totalBoxes > truckSize) return 0;Discard combinations exceeding truck capacity early

maxUnits = Math.max(maxUnits, helper(...))Keep track of maximum units found among all combinations

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int helper(const vector<vector<int>>& boxTypes, int truckSize, int index, vector<int>& counts) {
    if (index == boxTypes.size()) {
        int totalBoxes = 0, totalUnits = 0;
        for (int i = 0; i < counts.size(); i++) {
            totalBoxes += counts[i];
            if (totalBoxes > truckSize) return 0;
            totalUnits += counts[i] * boxTypes[i][1];
        }
        return totalUnits;
    }
    int maxUnits = 0;
    int maxCount = min(boxTypes[index][0], truckSize);
    for (int c = 0; c <= maxCount; c++) {
        counts[index] = c;
        maxUnits = max(maxUnits, helper(boxTypes, truckSize, index + 1, counts));
    }
    return maxUnits;
}

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    vector<int> counts(boxTypes.size(), 0);
    return helper(boxTypes, truckSize, 0, counts);
}

int main() {
    vector<vector<int>> boxTypes = {{1,3},{2,2},{3,1}};
    int truckSize = 4;
    cout << maximumUnits(boxTypes, truckSize) << endl; // Output: 8
    return 0;
}

Line Notes

if (index == boxTypes.size())Base case: all box types processed

for (int c = 0; c <= maxCount; c++)Try all possible counts for current box type from 0 to maxCount

if (totalBoxes > truckSize) return 0;Prune invalid combinations exceeding capacity early

maxUnits = max(maxUnits, helper(...))Update max units with best found so far

function maximumUnits(boxTypes, truckSize) {
    let maxUnits = 0;
    const n = boxTypes.length;
    function helper(index, counts) {
        if (index === n) {
            let totalBoxes = 0, totalUnits = 0;
            for (let i = 0; i < n; i++) {
                totalBoxes += counts[i];
                if (totalBoxes > truckSize) return 0;
                totalUnits += counts[i] * boxTypes[i][1];
            }
            return totalUnits;
        }
        let maxUnitsLocal = 0;
        let maxCount = Math.min(boxTypes[index][0], truckSize);
        for (let c = 0; c <= maxCount; c++) {
            counts[index] = c;
            maxUnitsLocal = Math.max(maxUnitsLocal, helper(index + 1, counts));
        }
        return maxUnitsLocal;
    }
    return helper(0, new Array(n).fill(0));
}

// Example usage
console.log(maximumUnits([[1,3],[2,2],[3,1]], 4)); // Output: 8

Line Notes

if (index === n)Base case: all box types considered

for (let c = 0; c <= maxCount; c++)Try all counts for current box type from 0 to maxCount

if (totalBoxes > truckSize) return 0;Discard invalid combinations exceeding truck capacity

maxUnitsLocal = Math.max(maxUnitsLocal, helper(...))Track maximum units found among all combinations

⏱

Complexity

TimeO((truckSize+1)^n) exponential

SpaceO(n) recursion stack and counts array

We try all combinations of counts for each box type up to truckSize, leading to exponential time.

💡 For n=3 and truckSize=4, this means checking up to 5^3=125 combinations, which grows quickly and is impractical for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate greedy solutions.

🧠

Sorting + Greedy Pick

💡 This approach sorts box types by units per box descending and greedily picks boxes from the highest unit box type until the truck is full. It is intuitive and efficient.

Intuition

To maximize units, always pick boxes from the type with the highest units per box first until the truck is full or that type is exhausted.

Algorithm

1. Sort boxTypes by units per box in descending order.
2. Initialize totalUnits and remaining truckSize.
3. Iterate over sorted boxTypes, pick min(boxes, remaining truckSize).
4. Add units from picked boxes to totalUnits and reduce truckSize.
5. Return totalUnits after truck is full or all boxes considered.

💡 The algorithm is straightforward but requires careful sorting and iteration to avoid off-by-one errors.

</>

Code

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
        if truckSize == 0:
            break
    return totalUnits

# Example usage
if __name__ == '__main__':
    boxTypes = [[1,3],[2,2],[3,1]]
    truckSize = 4
    print(maximumUnits(boxTypes, truckSize))  # Output: 8

Line Notes

boxTypes.sort(key=lambda x: x[1], reverse=True)Sort box types by units per box descending to prioritize high-value boxes

for boxes, units in boxTypes:Iterate over each box type in sorted order

take = min(boxes, truckSize)Pick as many boxes as possible without exceeding truck capacity

totalUnits += take * unitsAdd units from picked boxes to total

truckSize -= takeReduce remaining truck capacity

if truckSize == 0: breakStop if truck is full to avoid unnecessary iterations

import java.util.*;

public class MaximumUnits {
    public static int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int totalUnits = 0;
        for (int[] box : boxTypes) {
            int take = Math.min(box[0], truckSize);
            totalUnits += take * box[1];
            truckSize -= take;
            if (truckSize == 0) break;
        }
        return totalUnits;
    }

    public static void main(String[] args) {
        int[][] boxTypes = {{1,3},{2,2},{3,1}};
        int truckSize = 4;
        System.out.println(maximumUnits(boxTypes, truckSize)); // Output: 8
    }
}

Line Notes

Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);Sort box types descending by units per box

for (int[] box : boxTypes)Iterate over sorted box types

int take = Math.min(box[0], truckSize);Pick max boxes possible without exceeding capacity

totalUnits += take * box[1];Add units from picked boxes

truckSize -= take;Update remaining truck capacity

if (truckSize == 0) break;Stop when truck is full to save time

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1];
    });
    int totalUnits = 0;
    for (auto& box : boxTypes) {
        int take = min(box[0], truckSize);
        totalUnits += take * box[1];
        truckSize -= take;
        if (truckSize == 0) break;
    }
    return totalUnits;
}

int main() {
    vector<vector<int>> boxTypes = {{1,3},{2,2},{3,1}};
    int truckSize = 4;
    cout << maximumUnits(boxTypes, truckSize) << endl; // Output: 8
    return 0;
}

Line Notes

sort(boxTypes.begin(), boxTypes.end(), ...Sort box types by units per box descending

for (auto& box : boxTypes)Iterate over sorted box types

int take = min(box[0], truckSize);Pick as many boxes as possible without exceeding capacity

totalUnits += take * box[1];Add units from picked boxes

truckSize -= take;Update remaining truck capacity

if (truckSize == 0) break;Stop when truck is full to avoid extra work

function maximumUnits(boxTypes, truckSize) {
    boxTypes.sort((a, b) => b[1] - a[1]);
    let totalUnits = 0;
    for (const [boxes, units] of boxTypes) {
        const take = Math.min(boxes, truckSize);
        totalUnits += take * units;
        truckSize -= take;
        if (truckSize === 0) break;
    }
    return totalUnits;
}

// Example usage
console.log(maximumUnits([[1,3],[2,2],[3,1]], 4)); // Output: 8

Line Notes

boxTypes.sort((a, b) => b[1] - a[1]);Sort box types descending by units per box

for (const [boxes, units] of boxTypes)Iterate over sorted box types

const take = Math.min(boxes, truckSize);Pick max boxes possible without exceeding capacity

totalUnits += take * units;Add units from picked boxes

truckSize -= take;Update remaining truck capacity

if (truckSize === 0) break;Stop when truck is full to save computation

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort implementation

Sorting takes O(n log n), then a single pass over boxTypes is O(n).

💡 For n=100000, sorting is efficient and picking boxes is linear, making this approach scalable.

Interview Verdict: Accepted

This is the optimal and accepted approach for this problem in interviews.

🧠

Greedy with Early Stopping and Inline Calculation

💡 This approach is a slight optimization of the previous by stopping early and calculating units inline without extra variables, demonstrating clean and efficient code.

Intuition

Same greedy idea but with minimal variables and early break to reduce overhead.

Algorithm

1. Sort boxTypes by units per box descending.
2. Initialize totalUnits to 0.
3. Iterate over boxTypes, pick boxes up to truckSize.
4. Add units directly to totalUnits and reduce truckSize.
5. Break early if truckSize reaches zero.
6. Return totalUnits.

💡 This approach is easier to read and write, showing mastery of the greedy pattern.

</>

Code

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

# Example usage
if __name__ == '__main__':
    boxTypes = [[1,3],[2,2],[3,1]]
    truckSize = 4
    print(maximumUnits(boxTypes, truckSize))  # Output: 8

Line Notes

boxTypes.sort(key=lambda x: x[1], reverse=True)Sort descending by units per box to prioritize

if truckSize == 0: breakStop early if truck is full to save time

take = min(boxes, truckSize)Pick as many boxes as possible without exceeding capacity

totalUnits += take * unitsAdd units from picked boxes

truckSize -= takeUpdate remaining truck capacity

import java.util.*;

public class MaximumUnits {
    public static int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
        int totalUnits = 0;
        for (int[] box : boxTypes) {
            if (truckSize == 0) break;
            int take = Math.min(box[0], truckSize);
            totalUnits += take * box[1];
            truckSize -= take;
        }
        return totalUnits;
    }

    public static void main(String[] args) {
        int[][] boxTypes = {{1,3},{2,2},{3,1}};
        int truckSize = 4;
        System.out.println(maximumUnits(boxTypes, truckSize)); // Output: 8
    }
}

Line Notes

if (truckSize == 0) break;Early stop when truck is full

int take = Math.min(box[0], truckSize);Pick max boxes possible without exceeding capacity

totalUnits += take * box[1];Add units from picked boxes

truckSize -= take;Update remaining truck capacity

Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);Sort descending by units per box

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1];
    });
    int totalUnits = 0;
    for (auto& box : boxTypes) {
        if (truckSize == 0) break;
        int take = min(box[0], truckSize);
        totalUnits += take * box[1];
        truckSize -= take;
    }
    return totalUnits;
}

int main() {
    vector<vector<int>> boxTypes = {{1,3},{2,2},{3,1}};
    int truckSize = 4;
    cout << maximumUnits(boxTypes, truckSize) << endl; // Output: 8
    return 0;
}

Line Notes

if (truckSize == 0) break;Stop early when truck is full

int take = min(box[0], truckSize);Pick max boxes possible without exceeding capacity

totalUnits += take * box[1];Add units from picked boxes

truckSize -= take;Update remaining truck capacity

sort(boxTypes.begin(), boxTypes.end(), ...Sort descending by units per box

function maximumUnits(boxTypes, truckSize) {
    boxTypes.sort((a, b) => b[1] - a[1]);
    let totalUnits = 0;
    for (const [boxes, units] of boxTypes) {
        if (truckSize === 0) break;
        const take = Math.min(boxes, truckSize);
        totalUnits += take * units;
        truckSize -= take;
    }
    return totalUnits;
}

// Example usage
console.log(maximumUnits([[1,3],[2,2],[3,1]], 4)); // Output: 8

Line Notes

if (truckSize === 0) break;Early stop when truck is full

const take = Math.min(boxes, truckSize);Pick max boxes possible without exceeding capacity

totalUnits += take * units;Add units from picked boxes

truckSize -= take;Update remaining truck capacity

boxTypes.sort((a, b) => b[1] - a[1]);Sort descending by units per box

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort implementation

Sorting dominates time complexity; iteration is linear.

💡 This approach is efficient and clean, suitable for large inputs and interviews.

Interview Verdict: Accepted

This approach is the cleanest and most interview-friendly solution.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the sorting + greedy approach (Approach 2 or 3) because it is optimal, efficient, and easy to explain.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O((truckSize+1)^n)	O(n)	Yes (deep recursion)	N/A	Mention only - never code due to inefficiency
2. Sorting + Greedy Pick	O(n log n)	O(1) or O(n)	No	N/A	Code this approach for optimal solution
3. Greedy with Early Stopping and Inline Calculation	O(n log n)	O(1) or O(n)	No	N/A	Code this for clean and efficient solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain your reasoning clearly during interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss inefficiency and motivate greedy approach.Step 4: Present sorting + greedy solution with code.Step 5: Optimize code for clarity and early stopping.Step 6: Test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your ability to identify greedy patterns, implement sorting and iteration correctly, and handle edge cases efficiently.

Common Follow-ups

• What if truckSize is very large? → The approach still works efficiently.
• Can you solve it without sorting? → No, sorting is essential to pick highest units first.

💡 Follow-ups test your understanding of greedy necessity and scalability.

🔍

Pattern Recognition

When to Use

1) Problem involves maximizing/minimizing a value with limited capacity. 2) Items have a value per unit or weight. 3) You can pick partial or whole items (here whole boxes). 4) Greedy choice of highest value per unit leads to optimal solution.

Signature Phrases

maximum total number of unitstruckSizenumber of units per box

NOT This Pattern When

0/1 Knapsack - requires DP because partial picking is not allowed and greedy fails

Similar Problems

Fractional Knapsack - similar greedy sorting by value per weightAssign Cookies - greedy allocation by sizeCar Pooling - interval scheduling greedy

Practice

1. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?

easy

A. 534330

B. 53430

C. 534303

D. 534330

Solution

1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

   We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

   Concatenate to get '534330'. The check for leading zero is false since first is '5'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation order matches expected largest number [OK]

Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]

Common Mistakes:

• Off-by-one in sorting
• Ignoring leading zero case
• Misordering '30' and '3'

2. What is the time complexity of the optimal greedy solution using prefix sums and two pointers for the Gas Station (Circular) problem, given n stations?

medium

A. O(n²) because of nested loops over stations

B. O(n log n) due to sorting or binary search in prefix sums

C. O(n) because prefix sums allow constant time range queries and a single pass

D. O(n) but with O(n) extra space for prefix sums

Solution

1. Step 1: Analyze prefix sums computation

   Computing prefix sums takes O(2n) = O(n) time.

2. Step 2: Analyze the single pass check

   The loop checking prefix[i+n] - prefix[i] runs n times, each in O(1), total O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with prefix sums yields linear time [OK]

Hint: Prefix sums enable O(1) range queries, total O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking sorting is needed
• Confusing space with time complexity

3. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why is the following common misconception incorrect? Misconception: The time complexity is O(n^2) because for each index, you might check all reachable next indices.

medium

A. O(n) because the algorithm iterates through the array once, updating max reachable index

B. O(n log n) due to sorting or binary search involved in jump calculations

C. O(n^2) because each index can jump to multiple next indices

D. O(n) but with O(n) auxiliary space for memoization

Solution

1. Step 1: Identify the algorithm's iteration pattern

   The greedy solution iterates through the array once, updating a single variable maxReach without nested loops.

2. Step 2: Explain why O(n^2) is incorrect

   Unlike brute force, it does not explore all jumps explicitly; it only tracks the furthest reachable index, so no nested iteration occurs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass through array -> O(n) time, no nested loops [OK]

Hint: Greedy uses one pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming nested loops due to jumps

4. Suppose now you can reuse sticks after merging (i.e., merged sticks remain available for future merges without removal). Which modification to the algorithm correctly computes the minimum cost to connect all sticks under this new rule?

hard

A. Use a dynamic programming approach to consider all merge sequences

B. Sort sticks once and merge sticks in ascending order without a heap

C. The problem becomes ill-defined; no algorithm can guarantee minimum cost with reuse

D. Use the same min-heap approach but do not remove merged sticks from the heap

Solution

1. Step 1: Understand reuse impact

   If sticks can be reused infinitely, merges do not reduce the number of sticks, so the problem changes fundamentally.

2. Step 2: Analyze problem feasibility

   Because sticks remain after merging, the process can continue indefinitely, making minimum total cost undefined or infinite.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reuse breaks the problem constraints -> no minimal cost solution [OK]

Hint: Reusing sticks breaks problem constraints -> no minimal cost [OK]

Common Mistakes:

• Assuming min-heap still works without removing merged sticks
• Trying to sort once ignoring dynamic merges
• Attempting DP without problem redefinition

5. If tasks can be reused infinitely (i.e., unlimited supply of each task type), how should the Task Scheduler algorithm be modified to find the minimum total time with cooldown n?

hard

A. Use the same max-heap approach but reset frequencies after each full cycle

B. Calculate the minimal cycle length as (n + 1) and multiply by the number of unique tasks

C. Since tasks are infinite, schedule tasks in a fixed repeating pattern of length (n + 1) without heap

D. The problem reduces to scheduling one task repeatedly with cooldown, so total time is tasks count

Solution

1. Step 1: Understand infinite reuse implication

   With infinite supply, the scheduler can always pick a different task to fill cooldown slots.

2. Step 2: Optimal scheduling pattern

   Tasks can be scheduled in a fixed repeating pattern of length n + 1, cycling through unique tasks to avoid idle time.

3. Step 3: Algorithm modification

   No need for frequency tracking or heap; just cycle through unique tasks repeatedly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite tasks allow fixed pattern scheduling without heap [OK]

Hint: Infinite tasks -> fixed repeating pattern of length n+1 [OK]

Common Mistakes:

• Trying to use heap with infinite tasks
• Multiplying cycles incorrectly
• Ignoring cooldown constraints