call(back)
Algorithms & Data StructureseasySign in to star problems

Pick the Query Type That Maximises Revenue

Each query type i takes durations[i] minutes and earns revenues[i] when it completes. You must commit to one type and run it back to back for k minutes; a run that does not finish inside the budget earns nothing. Return the index of the type with the highest total revenue, the smallest index on ties, or -1 if no type can complete even once.

bestQueryType([3, 5, 2], [10, 20, 5], 10)  ->  1    // 2 runs × 20 = 40
bestQueryType([4, 4], [7, 7], 8)           ->  0    // tie, lowest index
bestQueryType([10], [100], 5)              ->  -1

Hints

Hint 1

Score type i as floor(k / durations[i]) × revenues[i]; keep the first index that attains the maximum, and require that maximum to be positive.

Asked at