[Greedy] LC 1029. Two City Scheduling

https://leetcode.com/problems/two-city-scheduling

Highlights

• A greedy approach which (almost) always require sorting

Goal

• Given an array of size 2n, develop the optimal selection strategy to select n people for group A, and another n people for group B

Strategy

• Since this is a greedy approach, we can sort the given array by (a-b) in ascending order
• The sorted array should have elements that cost the least in group A at the beginning
• We are splitting into two groups, and each group has n element. Hence the first n elements better selected to A, and the other half n elements better goes to B

Time & Space Complexity

• Time: since we used a sorting algorithm → nlogn
• Space: O(1) since we only increment the res and not taking any extra space

Code

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        s = sorted(costs, key = lambda x: x[0] - x[1])
        
        res = 0
        increment = math.floor(len(costs)/2)
        
        for i in range(increment):
            res+= s[i][0]
            res+= s[i+increment][1]
            
        return s