1029. Two City Scheduling - Explanation

Description

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCost[i], bCost[i]], the cost of flying the i-th person to city a is aCost[i], and the cost of flying the i-th person to city b is bCost[i].

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:

2 * n == costs.length
2 <= costs.length <= 100
costs.length is even.
1 <= aCost[i], bCost[i] <= 1000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs) // 2

        def dfs(i, aCount, bCount):
            if i == len(costs):
                return 0

            res = float("inf")
            if aCount > 0:
                res = costs[i][0] + dfs(i + 1, aCount - 1, bCount)

            if bCount > 0:
                res = min(res, costs[i][1] + dfs(i + 1, aCount, bCount - 1))
            return res

        return dfs(0, n, n)

Time & Space Complexity

Time complexity: $O(2 ^ N)$
Space complexity: $O(N)$ for recursion stack.

Where $N$ is the size of the array $costs$ .

2. Dynamic Programming (Top-Down)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs) // 2
        dp = [[-1] * (n + 1) for _ in range(n + 1)]

        def dfs(i, aCount, bCount):
            if i == len(costs):
                return 0
            if dp[aCount][bCount] != -1:
                return dp[aCount][bCount]

            res = float("inf")
            if aCount > 0:
                res = costs[i][0] + dfs(i + 1, aCount - 1, bCount)
            if bCount > 0:
                res = min(res, costs[i][1] + dfs(i + 1, aCount, bCount - 1))

            dp[aCount][bCount] = res
            return res

        return dfs(0, n, n)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Where $n$ is the half of the size of the array $costs$ .

3. Dynamic Programming (Bottom-Up)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs) // 2
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for aCount in range(n + 1):
            for bCount in range(n + 1):
                i = aCount + bCount
                if i == 0:
                    continue

                dp[aCount][bCount] = float("inf")
                if aCount > 0:
                    dp[aCount][bCount] = min(dp[aCount][bCount], dp[aCount - 1][bCount] + costs[i - 1][0])
                if bCount > 0:
                    dp[aCount][bCount] = min(dp[aCount][bCount], dp[aCount][bCount - 1] + costs[i - 1][1])

        return dp[n][n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

Where $n$ is the half of the size of the array $costs$ .

4. Dynamic Programming (Space Optimized)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs) // 2
        dp = [0] * (n + 1)

        for aCount in range(n + 1):
            for bCount in range(n + 1):
                i = aCount + bCount
                if i == 0:
                    continue

                tmp = dp[bCount]
                dp[bCount] = float("inf")
                if aCount > 0:
                    dp[bCount] = min(dp[bCount], tmp + costs[i - 1][0])
                if bCount > 0:
                    dp[bCount] = min(dp[bCount], dp[bCount - 1] + costs[i - 1][1])

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

Where $n$ is the half of the size of the array $costs$ .

5. Greedy

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        diffs = []
        for c1, c2 in costs:
            diffs.append([c2 - c1, c1, c2])

        diffs.sort()
        res = 0
        for i in range(len(diffs)):
            if i < len(diffs) // 2:
                res += diffs[i][2]
            else:
                res += diffs[i][1]

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

6. Greedy (Optimal)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[1] - x[0])
        n, res = len(costs) // 2, 0

        for i in range(n):
            res += costs[i][1] + costs[i + n][0]
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.