Problem1 Solution

Maximize Inventory Adjustments Solution

Topics Involved / Prerequisites

• Greedy Algorithms

• Array Sorting

Overview

1. To maximize the number of shipments processed,
2. we must build our inventory as much as possible before fulfilling any orders. By processing all positive restocks first,
3. we achieve the highest possible inventory peak. We can then process the negative adjustments from the smallest impact to the largest until our inventory runs out.

Approach

1. Segregating and Building Since we are allowed to process the shipments in an optimal order, we should immediately grab all the positive adjustments. We iterate through the array, adding all positive values to our running inventory total and incrementing our processed count. We store all the negative adjustments in a separate list.

2. Fulfilling Safely Once our inventory is at its absolute maximum, we sort our list of negative adjustments in ascending order based on their absolute value. This allows us to fulfill the "cheapest" shipments first. We subtract them from our inventory one by one. If subtracting a shipment would cause the inventory to drop to 0 or below, we immediately halt and return our current count, as the rules require a strictly positive inventory.

function maxShipments(n, inventoryAdjustments):
    inventory = 0
    processedCount = 0
    create an empty array 'negatives'
    
    // Step 1: Process all positive shipments first
    for each adj in inventoryAdjustments:
        if adj > 0:
            inventory = inventory + adj
            processedCount = processedCount + 1
        else if adj < 0:
            // Store the absolute cost of the negative shipment
            negatives.push_back(abs(adj))
            

    for each cost in negatives:
        // Inventory must remain strictly greater than 0
        if inventory - cost > 0:
            inventory = inventory - cost
            processedCount = processedCount + 1
        else:
            break // Halt operations if we can't process it safely
            
    return processedCount

Time Complexity

• Time: O(Nlog N) - Sorting the negative adjustments is the bottleneck. The array traversals are strictly linear.

• Space: O(N) - In the worst-case scenario, all shipments are negative, meaning we store all N elements in our separate list.

Problem2 -Maximum Storage Efficiency Solution

Topics Involved / Prerequisites

• Binary Search on Answer

• Greedy Math

Overview

1. We need to allocate the storage units among the tasks so that the minimum segments per unit is maximized.
2. By binary searching the target minimum efficiency, we can quickly verify if a given segment threshold is achievable.
3. A threshold is valid if the sum of the maximum allowed units per task for that threshold is greater than or equal to the total units available.

Approach

1. Binary Search the Answer

The lowest possible storage efficiency is 1, and the absolute maximum is the size of the smallest task (since a task must have at least one unit, the highest minimum load it can have is all of its segments in a single unit). We can binary search an efficiency target X within this range.

2. Validating the Threshold

For a guessed efficiency X, how many units can a task utilize without any single unit dropping below X segments? The math is exactly floor (segments / X ). We calculate this maximum allowed unit count for every task and sum them up. If any task gets 0 units, the guess is invalid. If the total allowed units across all tasks is >= m, then the threshold X is achievable!

function canAchieve(n, m, num_segments, minEfficiency):
    totalUnitsAllowed = 0
    
    for i from 0 to n - 1:
       
        allowedUnits = num_segments[i] / minEfficiency
        
       
        if allowedUnits == 0:
            return false
            
        totalUnitsAllowed = totalUnitsAllowed + allowedUnits
        
    // Can we deploy all m units without dipping below the requested efficiency?
    return totalUnitsAllowed >= m

function maxStorageEfficiency(n, m, num_segments):
    if m < n:
        return 0
        
    low = 1
    high = infinity
    
   
    for i from 0 to n - 1:
        high = min(high, num_segments[i])
        
    ans = 0
    
    while low <= high:
        mid = low + (high - low) / 2
        
        if canAchieve(n, m, num_segments, mid):
            ans = mid
            low = mid + 1  // Guess is valid, push for a higher efficiency
        else:
            high = mid - 1 // Guess is too ambitious, lower the target
            
    return ans

Time Complexity

• Time: O(N log S) - Where S is the minimum value in the num_segments array. We perform an O(N) check for every step of our binary search.

• Space: O(1) - We only use a few basic variables to track our search bounds and unit sums.