Code RoomPareto optimal routes
HardPrep Room Coding #4917

Pareto optimal routes

CodingAlgorithms & data structuresMid–Staff~38 min

A wholesale carrier publishes thousands of interconnect routes to the same destination. Route i charges setup_fees[i] cents to open a call plus rates[i] cents for every minute the call lasts, so a call of t minutes costs setup_fees[i] + rates[i] * t cents. A duration is any value at or above zero and need not be a whole number of minutes. The sales page should carry only routes a customer could rationally pick, so route i belongs on it when some duration exists at which it costs strictly less than every other route. A route that only ever ties for cheapest does not belong. The two lists have the same length and hold values at or above zero. Return the indices of the routes that belong, in increasing order, or an empty list when none do.

Implement
routes_worth_listing(setup_fees: list[int], rates: list[int]) → list[int]
Examples
in[[1200,600,300],[2,5,12]]out[0,1,2]
in[[0,1,2],[3,2,1]]out[0,2]
in[[500,500],[4,4]]out[]
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 38 min
InputExpectedGot
[[1200,600,300],[2,5,12]][0,1,2]not run yetsample
[[0,1,2],[3,2,1]][0,2]not run yetsample
[[500,500],[4,4]][]not run yetsample