K Closest Open Places
Someone searches "pharmacy" on a maps app at 23:00. The worst answer is a list that starts with three pharmacies that closed hours ago. You are writing the step that, given the places matching a search, returns the k closest ones that are open right now.
The search area is small enough to treat as flat, so positions are integer metres on a local grid. The user stands at (x, y). Place i stands at (xs[i], ys[i]) and its opening hours are opens[i] and closes[i], both minutes since midnight (0 to 1439). At minute minute, place i is open when:
opens[i] < closes[i]:opens[i] <= minute < closes[i];opens[i] > closes[i](it closes after midnight):minute >= opens[i]orminute < closes[i];opens[i] == closes[i]: always, it is open around the clock.
Return the indices of the k open places closest to the user (straight-line distance), nearest first. Places at the same distance are ordered by index. If fewer than k places are open, return all of them.
Example
The user is at (0, 0) at minute 600 (10:00) and wants k = 2. Place 0 at (3, 4) is open 08:00 to 20:00, place 1 at (1, 1) only overnight, place 2 at (-2, 0) around the clock, place 3 at (0, 5) closed at exactly 10:00, and place 4 at (5, 0) opens at exactly 10:00. The open ones are 0, 2 and 4, at distances 5, 2 and 5. The answer is [2, 0]: place 0 wins the tie with place 4 on index.
[ "0", "0", "600", "2", "[3,1,-2,0,5]", "[4,1,0,5,0]", "[480,1320,0,540,600]", "[1200,360,0,600,900]" ]
Explanation. The example.
[ "0", "0", "1380", "3", "[3,1,-2,0,5]", "[4,1,0,5,0]", "[480,1320,0,540,600]", "[1200,360,0,600,900]" ]
Explanation. At 23:00 the overnight place is open, and only two places are open at all.
[ "10", "10", "0", "1", "[10,10]", "[10,11]", "[1320,0]", "[360,0]" ]
Explanation. Overnight hours include midnight.
[ "0", "0", "100", "1", "[1]", "[1]", "[600]", "[700]" ]
Explanation. Nothing is open.
[ "0", "0", "500", "3", "[1,0,-1,0]", "[0,1,0,-1]", "[0,0,0,0]", "[0,0,0,0]" ]
Explanation. Equal distances: lower indices first.
[ "-1000000", "-1000000", "0", "2", "[1000000,0,-999999]", "[1000000,0,-1000000]", "[0,0,0]", "[0,0,0]" ]
Explanation. Squared distances beyond 32-bit integers.
[ "0", "0", "360", "5", "[1,2,3]", "[0,0,0]", "[1320,360,0]", "[360,1320,0]" ]
Explanation. An overnight place has closed at its closing minute; a day place has just opened.
[ "5", "5", "720", "3", "[5,6,4,5,7,2,5]", "[6,5,4,8,7,5,5]", "[700,730,0,600,1000,100,1439]", "[800,800,0,720,800,1439,1]" ]
Explanation. Places closing now, opening later and open overnight, mixed.
Follow-up: The same search is repeated as the user pans the map, each time with a slightly different `(x, y)` and the same thousands of places. What would you precompute so each pan costs far less than a pass over every place?
- `1 <= xs.length <= 10^5`, and `xs`, `ys`, `opens` and `closes` have the same length. - `-10^6 <= x, y, xs[i], ys[i] <= 10^6` - `0 <= minute, opens[i], closes[i] <= 1439` - `1 <= k <= xs.length`
- Views
- 2