Maximize Warehouse Query Profit

Overview

The problem asks us to select a single query type from a list and execute it repeatedly within a fixed time window $k$. For each query type, we calculate how many times it can fully complete within $k$ minutes and multiply that by its individual profit. Our goal is to find the maximum possible profit and the index of the query type that achieves it.

The tie-breaking rule is crucial: if two query types yield the same maximum profit, we must return the one that appeared earlier in the input list (the smallest index).

Brute Force

Since we only need to pick exactly one query type to run repeatedly, a brute-force approach involves iterating through every query type provided in the list, calculating its potential profit, and keeping track of the best one found so far.

For each query $i$ at index $idx$:

1. Extract executionTime and profitPerExecution.
2. Check if the query can be run at least once (i.e., executionTime <= k).
3. Calculate total executions: executions = k // executionTime.
4. Calculate total profit: current_profit = executions * profitPerExecution.
5. Update the global maximum if current_profit is strictly greater than the previous maximum.

By using a "strictly greater than" (>) comparison, we naturally respect the requirement to keep the smallest index in case of a tie, as later indices with the same profit will not overwrite the first one recorded.

def maximizeQueryProfit(queries: list[list[int]], k: int) -> list[int]:
    max_profit = 0
    best_index = -1
    
    for i in range(len(queries)):
        execution_time = queries[i][0]
        profit_per_run = queries[i][1]
        
        # Check if the query can be executed at least once
        if execution_time <= k:
            executions = k // execution_time
            total_profit = executions * profit_per_run
            
            # If this profit is better than what we've seen, update.
            # Using '>' ensures we keep the smallest index for ties.
            if total_profit > max_profit:
                max_profit = total_profit
                best_index = i
            # Special case for the first valid query found if max_profit is 0
            elif max_profit == 0 and best_index == -1:
                max_profit = total_profit
                best_index = i
                
    return [max_profit, best_index]

Time complexity: O(N) — We perform a single linear scan through the queries list, where N is the number of query types. Space complexity: O(1) — We only store a few integer variables regardless of the input size.

Optimal Approach

The brute force approach described above is actually the optimal approach for this problem. Since we must consider every query type at least once to ensure we haven't missed a more profitable option, we cannot achieve a time complexity better than $O(N)$.

We can refine the implementation slightly for cleanliness. By initializing max_profit to 0 and best_index to -1, we handle the "no query fits" case (Example 3) automatically.

def maximizeQueryProfit(queries: list[list[int]], k: int) -> list[int]:
    max_profit = 0
    best_index = -1
    
    for i, (exec_time, profit) in enumerate(queries):
        # If the query cannot even fit once, skip it
        if exec_time > k:
            continue
        
        # Calculate total profit using floor division
        num_executions = k // exec_time
        total_profit = num_executions * profit
        
        # Standard greedy update
        # Because we iterate from index 0 upwards, 
        # using '>' automatically preserves the smallest index for ties.
        if total_profit > max_profit:
            max_profit = total_profit
            best_index = i
        # Handle the case where the first valid query results in 0 profit 
        # (though constraints say profit >= 1)
        elif best_index == -1:
            max_profit = total_profit
            best_index = i
            
    return [max_profit, best_index]

Time complexity: O(N) — Each of the $N$ queries is processed exactly once. Space complexity: O(1) — No additional data structures are used; we only track the current maximum and its index.

Edge Cases

1. $k$ is smaller than all executionTime_i: The loop will finish without updating best_index, and the function will correctly return [0, -1].
2. Multiple queries have the same max profit: The if total_profit > max_profit condition ensures that only the first query found with that profit is stored.
3. Only one query type: The loop runs once and returns that query's profit if it fits within $k$.
4. Large $k$ or profits: The problem notes state the max profit fits in a 32-bit signed integer, so we don't need to worry about overflow in standard Python 3.

Fast