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 i
th 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
to cover k
cars from the rain. Why build just a singular roof and why only cover k
cars
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.
Parameters
pos
: A list of integers representing the positions of the cars.k
: The minimum amount of cars your roof should cover.
Result
- The minimum number of parking slots the roof needs to cover.
Examples
Example 1:
Input: pos = [2, 10, 8, 17]
, k = 3
Output: 9
Explanation: You need a roof spanning from 2
to 10
to cover the first three cars.
Constraints
1 <= n <= 10^5
1 <= k <= n
1 <= pos[i] <= 10^9
Try it yourself
Solution
Title
Script
Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem
Ipsum
has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.
Contrary to popular belief, Lorem
Ipsum
is not simply random text.
1 >>> a = [1, 2, 3] 2 >>> a[-1] 3 3