Teaching Kids Programming – Greedy Algorithm of Buying Cars

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers prices representing prices of cars for sale, and a budget k, return the maximum number of cars you can buy.

Constraints
n ≤ 100,000 where n is the length of prices
Example 1
Input
prices = [90, 30, 20, 40, 90]
k = 95
Output
3
Explanation
We can buy the cars with prices 30, 20, and 40.

Example 2
Input
prices = [60, 90, 55, 75]
k = 50
Output
0
Explanation
We cannot afford any of these cars.

Greedy Algorithm/Strategy of Purchasing

The Greedy Strategy: We always pick the smallest to purchase, then the next smallest, and then the next smallest.. This is guaranteed that we can purchase as many cars as possible.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def greedyAlgorithm(self, prices, budget):
        prices.sort()
        ans = 0
        for p in prices:
            if budget >= p:
                ans += 1
                budget -= p
            else:
                break
        return ans

class Solution:
    def greedyAlgorithm(self, prices, budget):
        prices.sort()
        ans = 0
        for p in prices:
            if budget >= p:
                ans += 1
                budget -= p
            else:
                break
        return ans

Sorting takes O(NLogN) time and the greedy algorithm takes O(N) and therefore the overall time complexity is O(NLogN) as the sorting dominates.

This is one special case of KnapSack problem where each item has a weight (price) and same value (worth of 1), and we have a bag that has a capacity (budget), our target is to pack as many items as possible in the knapsack.

–EOF (The Ultimate Computing & Technology Blog) —