Минимальное количество свопов, необходимых для того, чтобы K автомобилей прибыли в пункт назначения вовремя

Даны N автомобилей и целое число D , т.е. расстояние до пункта назначения. Все автомобили стартуют из одной и той же начальной точки и движутся к одной и той же точке назначения. Скорости каждого из автомобилей задаются массивом speed[] , а их соответствующие позиции в порядке возрастания задаются массивом position[]. Автомобиль, движущийся с меньшей скоростью, чем предыдущий, считается препятствием для другого. Задача состоит в том, чтобы заставить K автомобилей добраться до места назначения с минимальным количеством обменов за заданное время T. Автомобиль можно поменять местами только с автомобилем, следующим за ним, это можно сделать только с одним автомобилем.
Более одного свопа одновременно, но каждый своп считается отдельным свопом. Если K автомобилей не могут добраться до пункта назначения за заданное время, верните -1.

Примеры :

Input: N = 5, K= 3, D = 10, T = 5, position[] = {0, 2, 5, 6, 7}, speed[] = {1, 1, 1, 1, 4}
Output: 0
Explanation: No swaps would be required in this case as the speeds of all cars are in increasing order and last 3 cars can easily reach the destination in time T
 

Input: N = 5, K = 3, D = 10, T = 5, position[] = {0, 2, 3, 5, 7}, speed[] = {2, 1, 1, 1, 4}
Output: 2
Explanation: The car that has covered 0 distance i.e. at (0th index) is swapped with the car at 1st and 2nd index because none of them could reach destination on time. After swapping atleast 3 cars can reach the destination on time.
 

Input: N = 5, K = 3, D = 10, T = 5, position[] = {0, 2, 3, 4, 7}, speed[] = {2, 1, 1, 1, 4}
Output: -1
Explanation: K number of cars could not reach destination on time by making any number of swaps.

Подход : Задача может быть решена с использованием жадного подхода. Поскольку позиции каждого автомобиля даны в возрастающем порядке, лучший способ — начать итерацию с последнего автомобиля, оставляя счетчик доступным для автомобилей, которые могут добраться до места назначения вовремя, и встречное препятствие для автомобилей, которые не могут добраться. пункт назначения вовремя. Если автомобиль успевает добраться вовремя, добавьте количество препятствий к количеству обменов.
Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)
Вспомогательное пространство : O(1)