Twitter Online Assessment (OA) 2021 | Parking Dilemma
You are in charge of a linear parking lot. There are
n cars parked permanently in this
parking lot. The
ith car occupies the
pos[i]th parking slot.
You feel bad for the car owners of these cars, so you decided to build a roof
k cars from the rain. Why build just a singular roof and why only cover
instead of every car? You didn't get paid enough for this.
To save costs, you decide to minimize the size of the roof while still making sure you
cover at least
k cars. Given the positions of these
n cars and
k, find the minimum
number of parking slots this roof should cover.
pos: A list of integers representing the positions of the cars.
k: The minimum amount of cars your roof should cover.
- The minimum number of parking slots the roof needs to cover.
pos = [2, 10, 8, 17],
k = 3
Explanation: You need a roof spanning from
10 to cover the first three cars.
1 <= n <= 10^5
1 <= k <= n
1 <= pos[i] <= 10^9