A flock of sheep is running east along a straight, narrow road. Each one is running at its own constant speed. Whenever a sheep catches up to the one in front of it, it has to slow down and follow at the speed of the other sheep. You are in a mobile crane behind the flock, chasing the sheep towards the barn at the end of the road. The arm of the crane allows you to pick up any sheep momentarily, let the sheep behind it pass underneath, and place the picked-up sheep back down. This operation takes no time and can only be performed on a pair of sheep that are immediately next to each other, even if 3 or more sheep are in a row, one after the other.
Given the initial locations (Xi) at time 0 and natural speeds (Vi) of the sheep, as well as the location of the barn (B), what is the minimum number of swaps you need to perform with your crane in order to have at least K of the N sheep arrive at the barn no later than time T?
You may think of the sheep as points moving along a line. Even if 3 or more sheep are at the same location, next to each other, picking up one of them will only let one of the other two pass through. Any swap is instantaneous, which means that you may perform multiple swaps at the same time, but each one will count as a separate swap.
Example 1:
Input:
N=5
k=3
B=10
T=5
X[]={0,2,5 ,6, 7}
V[]={1,1,1,1,4}
Output:
0
Explanation:
Sheep 5,4 and 3 will reach the barn before or at 5 secs.
Example 2:
Input:
N=5
K=3
B=10
T=5
X[]={0,2,3,4,7}
V[]={2,1,1,1,4}
Output:
-1
Explanation:
At max 2 sheep can reach the barn within or at 5 secs so the
answer is -1.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumSwaps() which takes the array pos[],v[], N, K, B, and T as input parameters and returns the minimum number of swaps required. If it is not possible to make k sheep reach the barn before or on T seconds then return -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=10^{5}
1<=k<=N.
1 ≤ B ≤ 1,000,000,000
1 ≤ T ≤ 1,000
0 ≤ POS_{i} < B
1 ≤ V_{i} ≤ 100
All the POS_{i}'s will be in increasing order.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:


from typing import List

class Solution:

    def minimumSwaps(self,c : List[int], v : List[int],n : int,k : int,b : int, t : int) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		(good, bad, swap) = (0, 0, 0)
		for i in range(n - 1, -1, -1):
			if c[i] + v[i] * t >= b:
				good += 1
				swap += bad
			else:
				bad += 1
			if good >= k:
				break
		if good >= k:
			return swap
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		slow = 0
		ans = 0
		for i in range(n - 1, -1, -1):
			pos = c[i] + v[i] * t
			if pos >= b:
				k -= 1
				ans += slow
				if k == 0:
					return ans
			else:
				slow += 1
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		ans = 0
		ts = 0
		r = 0
		for i in range(n - 1, -1, -1):
			if r >= k:
				break
			d = v[i] * t
			if d >= b - c[i]:
				ans += ts
				r += 1
			else:
				ts += 1
		if r >= k:
			return ans
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		sheeps = [c[i] + v[i] * t for i in range(n)]
		count = 0
		for sheep in sheeps[::-1]:
			if sheep >= b:
				k -= 1
			else:
				count += k
			if k == 0:
				return count
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		swap = 0
		res = 0
		i = n - 1
		while k > 0 and i >= 0:
			dist = v[i] * t
			if dist >= b - c[i]:
				res += swap
				k -= 1
			else:
				swap += 1
			i -= 1
		if k > 0:
			return -1
		return res


from typing import List

class Solution:

	def minimumSwaps(self, pos: List[int], vi: List[int], n: int, k: int, b: int, t: int) -> int:
		swap_idx = -1
		flag = True
		ans = 0
		swaps = 0
		for i in range(n - 1, -1, -1):
			if vi[i] * t + pos[i] >= b:
				ans += 1
				if not flag:
					swaps += swap_idx - i
					swap_idx -= 1
					flag = False
				else:
					flag = True
			elif swap_idx == -1:
				flag = False
				swap_idx = i
			if ans >= k:
				return swaps
		return swaps if ans >= k else -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		df = 0
		sw = 0
		sh = 0
		ss = 0
		for i in range(n - 1, -1, -1):
			df = b - c[i]
			if t * v[i] >= df:
				sw += ss
				k -= 1
			else:
				ss += 1
			if k == 0:
				return sw
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		list1 = []
		minSwaps = 0
		for i in range(n):
			a = c[i] + v[i] * t
			if a >= b:
				list1.append(i)
		list1.sort(reverse=True)
		if len(list1) < k:
			return -1
		list1 = list1[:k]
		for i in range(len(list1)):
			minSwaps += n - list1[i] - i - 1
		return minSwaps


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		s = 0
		count = 0
		temp = [0] * n
		for i in range(n):
			temp[i] = t * v[i] + c[i]
		for i in range(n - 1, -1, -1):
			if temp[i] >= b:
				count += 1
				s += n - count - i
				if count == k:
					return s
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		(cnt, ans, swp) = (0, 0, 0)
		for i in range(n - 1, -1, -1):
			d = c[i] + v[i] * t
			if d >= b:
				cnt = cnt + 1
				ans = ans + swp
			else:
				swp = swp + 1
			if cnt == k:
				return ans
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		ans = 0
		ts = 0
		r = 0
		for i in range(n - 1, -1, -1):
			if r >= k:
				break
			d = v[i] * t
			if d >= b - c[i]:
				ans += ts
				r += 1
			else:
				ts += 1
		if r >= k:
			return ans
		return -1

	def minimumSwaps_bad(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		tpos = []
		lpos = []
		pos_cnt = [0] * b
		swaps = 0
		for (i, (pos, __v)) in enumerate(zip(c, v)):
			ttime = (b - pos) // __v + (1 if (b - pos) % __v else 0)
			if ttime <= t:
				tpos.append([i, pos, __v, ttime, pos + __v])
			else:
				lpos.append([i, pos, __v, ttime, pos + __v])
			pos_cnt[pos] += 1
		if len(tpos) >= k:
			tpos.sort(key=lambda x: x[4], reverse=True)
			while pos_cnt[b - 1] < k:
				for __sheep in lpos:
					pos_cnt[__sheep[1]] -= 1
					__sheep[1] += __sheep[2]
					pos_cnt[__sheep[1]] += 1
				for __sheep in tpos:
					if __sheep[1] < b - 1:
						pos_cnt[__sheep[1]] -= 1
						__sheep[1] += __sheep[2]
						if __sheep[1] >= b - 1:
							__sheep[1] = b - 1
						elif pos_cnt[__sheep[1]]:
							swaps += 1
						pos_cnt[__sheep[1]] += 1
					if pos_cnt[b - 1] >= k:
						break
		else:
			return -1
		return swaps


from typing import List

class Solution:

	def minimumSwaps(self, pos: List[int], v: List[int], n: int, k: int, barn: int, t: int) -> int:
		sheepUnableToReach = swap = 0
		for i in range(n - 1, -1, -1):
			canTravel = t * v[i] + pos[i]
			if canTravel >= barn:
				k -= 1
				swap += sheepUnableToReach
			else:
				sheepUnableToReach += 1
			if k == 0:
				return swap
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, pos: List[int], v: List[int], n: int, k: int, barn: int, t: int) -> int:
		sheep = slowSheep = crane = 0
		for i in range(n - 1, -1, -1):
			canTravel = t * v[i] + pos[i]
			if canTravel >= barn:
				sheep += 1
				crane += slowSheep
			else:
				slowSheep += 1
			if sheep >= k:
				break
		if sheep >= k:
			return crane
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, a: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		c = 0
		(ans, swap) = (0, 0)
		for i in range(n - 1, -1, -1):
			if b == a[i] or abs(b - a[i]) // v[i] <= t:
				ans += 1
				swap += c
				if ans >= k:
					break
			else:
				c += 1
		if ans >= k:
			return swap
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		l = []
		count = 0
		no = 0
		swap = 0
		for i in range(n - 1, -1, -1):
			if c[i] + t * v[i] >= b:
				if no > 0:
					swap += no
				count += 1
			else:
				no += 1
			if count == k:
				return swap
		if count < k:
			return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		swaps = 0
		reached = 0
		num = 0
		for i in range(n - 1, -1, -1):
			if (b - c[i]) / v[i] > t:
				num += 1
			elif (b - c[i]) / v[i] <= t:
				swaps += num
				reached += 1
				if reached == k:
					return swaps
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		count = 0
		x = 0
		j = 0
		for i in range(n - 1, -1, -1):
			if count == k:
				break
			if (b - c[i]) // v[i] <= t:
				count += 1
				x += j
			else:
				j += 1
		if count >= k:
			return x
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		swaps = 0
		count = 0
		for pos in range(n - 1, -1, -1):
			if v[pos] * t - (b - c[pos]) >= 0:
				k -= 1
				swaps += count
			else:
				count += 1
			if not k:
				return swaps
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		i = n - 1
		j = n - 1
		count = swaps = 0
		while i >= 0 and j >= 0 and (count < k):
			if c[i] + v[j] * t >= b:
				i -= 1
				j -= 1
				count += 1
				swaps += i - j
				if count == k:
					return swaps
			else:
				j -= 1
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		n = len(c)
		ans = 0
		slow_sheeps = 0
		for i in range(n - 1, -1, -1):
			total = c[i] + v[i] * t
			if total >= b:
				k -= 1
				ans += slow_sheeps
			else:
				slow_sheeps += 1
			if k == 0:
				return ans
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		temp = []
		out = 0
		for i in range(n):
			temp.append(c[i] + v[i] * t)
		flag = 0
		for i in range(n - 1, -1, -1):
			if temp[i] >= b:
				if flag > 0:
					out += flag
				k -= 1
			else:
				flag += 1
			if k == 0:
				return out
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, T: int) -> int:
		t = []
		for i in range(0, n):
			t.append((b - c[i]) / v[i])
		count = 0
		swaps = 0
		for i in range(n - 1, -1, -1):
			if t[i] <= T:
				swaps += n - 1 - i - count
				count += 1
				if count == k:
					return swaps
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		arr = []
		ans = 0
		for i in range(n):
			arr.append(c[i] + v[i] * t)
		count = 0
		for i in range(n - 1, -1, -1):
			if arr[i] >= b:
				if count > 0:
					ans += count
				k -= 1
			else:
				count += 1
			if k == 0:
				return ans
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		(s, r, o) = (0, 0, 0)
		for i in range(n - 1, -1, -1):
			if c[i] + t * v[i] >= b:
				r += 1
				s += o
			else:
				o += 1
			if r == k:
				return s
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		howmany = 0
		swaps = 0
		incre = 0
		for i in range(len(c) - 1, -1, -1):
			if howmany >= k:
				return swaps
			elif c[i] + t * v[i] < b:
				incre += 1
			elif c[i] + t * v[i] >= b:
				swaps += incre
				howmany += 1
		if howmany >= k:
			return swaps
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		swaps = 0
		blocker_sheeps = 0
		for i in range(n - 1, -1, -1):
			if k <= 0:
				break
			sheep_pos = c[i]
			sheep_velocity = v[i]
			if sheep_pos + sheep_velocity * t >= b:
				k -= 1
				swaps += blocker_sheeps
			else:
				blocker_sheeps += 1
		return swaps if k == 0 else -1


from typing import List
import math

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		(swaps, curr) = (0, 0)
		for i in range(n - 1, -1, -1):
			currentTime = math.ceil(float(b - c[i]) / v[i])
			if currentTime > t:
				curr += 1
				continue
			swaps += curr
			k -= 1
			if k == 0:
				return swaps
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		fixed_swap = 0
		min_swap = 0
		for i in range(n - 1, -1, -1):
			dis_covered = c[i] + v[i] * t
			if dis_covered >= b:
				k -= 1
				min_swap += fixed_swap
				if k == 0:
					return min_swap
			else:
				fixed_swap += 1
		return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		a = ba = s = 0
		for i in range(n - 1, -1, -1):
			if c[i] + v[i] * t >= b:
				a += 1
				s += ba
			else:
				ba += 1
			if a >= k:
				break
		if a >= k:
			return s
		else:
			return -1


from typing import List

class Solution:

	def minimumSwaps(self, c: List[int], v: List[int], n: int, k: int, b: int, t: int) -> int:
		sheeps_reached = 0
		sheeps_in_front = 0
		swap = 0
		for i in range(n)[::-1]:
			if b - c[i] <= v[i] * t:
				sheeps_reached += 1
				swap += sheeps_in_front
			else:
				sheeps_in_front += 1
			if sheeps_reached >= k:
				return swap
		return -1