Split Stay Options
MediumArrays ยท Airbnb
listings maps each listing name to the nights it is free (integers, in any order, possibly repeated). A trip needs every night from start to end inclusive.
Return every way to book it:
[name]when that listing is free for the whole trip.[first, second]for two different listings when, for some nightswithstart < s <= end,firstis free for nightsstarttos - 1andsecondfor nightsstoend.
List each option once, even if several s work or one listing alone already covers the trip. Sort the result ascending, comparing names as plain strings from left to right.
Example 1
- Input:
- listings = {"loft": [1, 2, 3, 4], "cabin": [3, 4, 5, 6], "barn": [1, 2, 3, 4, 5, 6]}, start = 2, end = 5
- Output:
- [["barn"], ["barn", "cabin"], ["loft", "barn"], ["loft", "cabin"]]
- Explanation
barncovers the trip alone, yet["barn", "cabin"]still counts.["loft", "cabin"]works for splits at 3, 4 and 5 but appears once.
Example 2
- Input:
- listings = {"a": [1, 3], "b": [2, 4]}, start = 1, end = 4
- Output:
- []
Example 3
- Input:
- listings = {"x": [5, 5, 9], "y": [5], "z": [4, 6]}, start = 5, end = 5
- Output:
- [["x"], ["y"]]
Constraints
0 <=number of listings<= 300- Each listing has at most
1000entries in its night list 1 <= start <= end <= 1000- Nights are integers from
0to1000; names are unique, non-empty strings