# LintCode: Number of restaurants

Number of restaurants

Similar Problems:

Description
Give a List of data representing the coordinates[x,y] of each restaurant. Customer’s coordinates are at the origin[0,0].Find out the n restaurants closest to the customer ,return their coordinates in the original order.

1. Coordinates in range [-1000,1000]
2. n>0

Example

```Given:

n = 2
List = [[0,0],[1,1],[2,2]]
Return:

[[0,0],[1,1]]
```

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```## Blog link: https://code.dennyzhang.com/number-of-restaurants
## Basic Ideas: maxheap
## Complexity: Time O(max(r, n*log(n)), Space O(n)
##              r = len(restaurant)
import heapq

class Solution:
"""
@param restaurant:
@param n:
@return: nothing
"""
def nearestRestaurant(self, restaurant, n):
if len(restaurant) < n: return []
l = []
heapq.heapify(l)
for i, r in enumerate(restaurant):
d = r[0]*r[0] + r[1]*r[1]
heapq.heappush(l, (-d, i))
if len(l) > n: heapq.heappop(l)

l.sort(key=lambda x:x[1])
res = []
for (_, i) in l: res.append(restaurant[i])
return res
```

Share It, If You Like It.