Toll Line Envelope Problem

Toll Line Envelope Problem — ExecCode Hard DSA Practice

Solve the Toll Line Envelope problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each highway company charges a linear toll ax + b for a trip of length x. A shipper, for several trip lengths, wants the cheapest company. A Li Chao tree (or convex hull trick, if slopes are monotone) maintains the lower envelope of lines and answers min at x. For each x in xs, return min over lines of ax+b. If there are no lines, return 0. You are given: lines — [a, b] companies xs — trip lengths to quote Return one minimum toll per x. All companies are always available; this is not versioned.

Examples

Input {'lines': [[1, 10], [-2, 8]], 'xs': [0, 3, -1]}; Output [8, 2, 9]. Input {'lines': [], 'xs': [4]}; Output [0]. Input {'lines': [[0, 5]], 'xs': [100]}; Output [5]

Constraints

x may be negative Empty lines → 0

Practice Toll Line Envelope free on ExecCode. Browse DSA problems, topic map, and placement guides.