Two price lists are given in ascending order: flights and hotels. A bundle is one flight price paired with one hotel price, and its cost is the sum. Return the k cheapest bundles as [flight, hotel] pairs, ordered from cheapest to dearest. When two bundles cost the same, the one with the smaller flight price comes first; if the flight prices are also equal, the smaller hotel price comes first. If there are fewer than k bundles in total, return them all.
Examples
Input: flights = [1, 7, 11], hotels = [2, 4, 6], k = 3
Output: [[1, 2], [1, 4], [1, 6]]
Explanation: costs 3, 5, 7. The next cheapest, [7, 2], costs 9.
Input: flights = [2, 5], hotels = [3, 4, 9], k = 4
Output: [[2, 3], [2, 4], [5, 3], [5, 4]]
Explanation: costs 5, 6, 8, 9; [2, 9] costs 11 and is left out.
Constraints
0 <= len(flights), len(hotels) <= 10**5, prices in[0, 10**9]1 <= k <= 10**5- Target complexity: O(k log k), independent of the product of the list lengths.
Goals
- Explore a sorted grid of pair sums by expanding a frontier
- Seed the heap with one entry per flight and advance the hotel index
- Reproduce an exact tie order using tuple keys