A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.
Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
 
Example 1:
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Example 2:
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

 
Constraints:

2n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCosti, bCosti <= 1000

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		dcosts = sorted(costs, key=lambda i: i[0] - i[1])
		n = len(costs) // 2
		acost = sum((c[0] for c in dcosts[:n]))
		bcost = sum((c[1] for c in dcosts[n:]))
		return acost + bcost


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		res = 0
		costs.sort(key=lambda x: x[1] - x[0], reverse=True)
		for i in range(len(costs) // 2):
			res += costs[i][0]
		for i in range(len(costs) // 2, len(costs)):
			res += costs[i][1]
		return res
		costs.sort(key=lambda x: x[1] - x[0], reverse=True)
		print(costs)
		ans = 0
		half = len(costs) // 2
		for i in range(half):
			ans += costs[i][0]
		for i in range(half, len(costs)):
			ans += costs[i][1]
		return ans


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		N = len(costs) // 2
		dp = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			dp[i][0] = dp[i - 1][0] + costs[i - 1][0]
		for j in range(1, N + 1):
			dp[0][j] = dp[0][j - 1] + costs[j - 1][1]
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				dp[i][j] = min(dp[i - 1][j] + costs[i + j - 1][0], dp[i][j - 1] + costs[i + j - 1][1])
		for row in dp:
			print(row)
		return dp[N][N]


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		lc = len(costs)
		c = lc // 2
		cost1 = 0
		cost2 = 0
		al = c
		bl = c
		for i in range(lc):
			for j in range(i + 1, lc):
				if abs(costs[i][0] - costs[i][1]) < abs(costs[j][0] - costs[j][1]):
					(costs[i], costs[j]) = (costs[j], costs[i])
		for i in range(lc):
			if costs[i][0] <= costs[i][1] and al > 0 or bl == 0:
				cost1 += costs[i][0]
				al -= 1
			elif bl > 0:
				cost1 += costs[i][1]
				bl -= 1
		al = c
		bl = c
		for i in range(lc):
			if costs[i][0] < costs[i][1] and al > 0 or bl == 0:
				cost2 += costs[i][0]
				al -= 1
			elif bl > 0:
				cost2 += costs[i][1]
				bl -= 1
		return min(cost1, cost2)


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		N = len(costs)
		dp = [0] + [float('inf')] * (N // 2)
		for i in range(1, N + 1):
			for j in range(N // 2, 0, -1):
				dp[j] = min(dp[j] + costs[i - 1][1], dp[j - 1] + costs[i - 1][0])
			dp[0] += costs[i - 1][1]
		return dp[-1]


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		n = len(costs)
		m = n // 2
		dp = [10 ** 6] * (m + 1)
		dp[m] = 0
		for i in range(n - 1, -1, -1):
			for j in range(m + 1):
				k = i - j
				c = 10 ** 6
				if j < m:
					c = min(c, costs[i][0] + dp[j + 1])
				if k < m:
					c = min(c, costs[i][1] + dp[j])
				dp[j] = c
		return dp[0]


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		m = len(costs)
		n = m // 2
		f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(min(n, i) + 1):
				f[i][j] = math.inf
				if j > 0:
					f[i][j] = costs[i - 1][0] + f[i - 1][j - 1]
				if i - j > 0:
					f[i][j] = min(f[i][j], costs[i - 1][1] + f[i - 1][j])
		return f[m][n]


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		c = []
		asum = 0
		for i in range(len(costs)):
			(a, b) = costs[i]
			price = b - a
			asum += a
			c.append(price)
		refunds = sorted(c)
		for i in range(len(refunds) // 2):
			asum += refunds[i]
		return asum


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		(A, B, n) = ([], [], len(costs) // 2)
		diff = []
		for (i, (a, b)) in enumerate(costs):
			diff.append((i, a - b))
			if a < b:
				A.append(i)
			else:
				B.append(i)
		flag = 0
		if len(A) > len(B):
			flag = 1
			diff = sorted(diff, key=lambda x: x[1], reverse=True)
			for (i, x) in diff:
				if x > 0 or i in B:
					continue
				B.append(i)
				if len(B) == n:
					break
		elif len(A) < len(B):
			flag = 2
			diff = sorted(diff, key=lambda x: x[1])
			for (i, x) in diff:
				if i in A:
					continue
				A.append(i)
				if len(A) == n:
					break
		res = 0
		for i in range(2 * n):
			(a, b) = costs[i]
			if flag == 1:
				res += b if i in B else a
			if flag == 2 or flag == 0:
				res += a if i in A else b
		return res


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		diff = [cost[1] - cost[0] for cost in costs]
		heapq.heapify(diff)
		s = 0
		for cost in costs:
			s += cost[0]
		for i in range(len(costs) // 2):
			s += heapq.heappop(diff)
		return s


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		diffs = []
		n = len(costs) / 2
		for (i, cost) in enumerate(costs):
			(a, b) = cost
			diff = abs(a - b)
			diffs.append((i, diff))
		diffs = sorted(diffs, key=lambda x: x[1], reverse=True)
		a_count = 0
		b_count = 0
		cost = 0
		print(diffs)
		for (i, diff) in diffs:
			city_a = True
			if costs[i][0] > costs[i][1]:
				if b_count < n:
					b_count += 1
					cost += costs[i][1]
				else:
					a_count += 1
					cost += costs[i][0]
			elif a_count < n:
				a_count += 1
				cost += costs[i][0]
			else:
				b_count += 1
				cost += costs[i][1]
		return cost


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		hashmap = collections.defaultdict(int)
		for item in costs:
			hashmap[tuple(item)] = abs(item[0] - item[1])
		print(hashmap)
		ll = sorted(hashmap, key=lambda x: -hashmap[x])
		print(ll)
		n = len(ll) // 2
		mincostA = []
		mincostB = []
		for i in range(2 * n):
			if len(mincostA) < n and len(mincostB) < n:
				if ll[i][0] < ll[i][1]:
					mincostA.append(ll[i][0])
				else:
					mincostB.append(ll[i][1])
			elif len(mincostA) < n:
				mincostA.append(ll[i][0])
			elif len(mincostB) < n:
				mincostB.append(ll[i][1])
		mincost = 0
		final = mincostA + mincostB
		for i in range(2 * n):
			mincost += final[i]
		return mincost


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		costs.sort(key=lambda x: x[0] - x[1])
		print(costs)
		firsthalf = costs[0:len(costs) // 2]
		secondhalf = costs[len(costs) // 2:]
		return sum((f[0] for f in firsthalf)) + sum((s[1] for s in secondhalf))


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		n = len(costs) // 2
		dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = dp[i - 1][0] + costs[i - 1][0]
		for j in range(1, n + 1):
			dp[0][j] = dp[0][j - 1] + costs[j - 1][1]
		for a in range(1, n + 1):
			for b in range(1, n + 1):
				dp[a][b] = min(dp[a - 1][b] + costs[a + b - 1][0], dp[a][b - 1] + costs[a + b - 1][1])
		return dp[n][n]


class Solution:

	def twoCitySchedCost(self, costs: List[List[int]]) -> int:
		sortedCosts = sorted(costs, key=lambda x: abs(x[0] - x[1]), reverse=True)
		numA = 0
		numB = 0
		res = 0
		for cost in sortedCosts:
			if numB >= len(sortedCosts) / 2:
				res += cost[0]
			elif numA >= len(sortedCosts) / 2:
				res += cost[1]
			elif cost[0] < cost[1]:
				res += cost[0]
				numA += 1
			else:
				res += cost[1]
				numB += 1
		return res