Can this greedy algorithm be more efficient?

Question

I'm studying for my exam coming up and I am practicing a problem that wants me to implement a greedy algorithm.

I am given an unsorted array of different weights where 0 < weight_i for all i. I have to place all of them such that I use the least number of piles. I can not place two weights in a pile where the one on top is greater than the one below. I also have to respect the ordering of the weights, so they must be placed in order. There is no height limit for the pile.

An example: If I have the weights {53, 21, 40, 10, 18} I cannot place 40 above 21 because the pile must be in descending order, and I cannot place 21 above 40 because that does not respect the order. An optimal solution would have pile 1: 53, 21, 10 and pile 2: 40 18

My general solution is iterate through the array and always pick the first pile the weight is allowed to go. I believe this would give me an optimal solution (although I haven't proved it yet). I could not find a counter example to this. But this would be O(n^2) because worst case I have to iterate through every element and every pile (I think)

My question is, is there a way to get this down to O(n) or O(nlogn)? If there is I'm just not seeing it and need some help.

Answer 1

Your algorithm will give a correct result.

Now note the following: when visiting the piles in order and stopping at the first one where the next value can be stacked, you will always have a situation where the stacks are ordered by their current top (last) value, in ascending order.

You can use this property to avoid an iteration of the piles from "left to right". Instead use a binary search, among the piles, to find that first pile that can take the next value.

This will give you a O(nlogn) time complexity.

Answer 2

Believe it or not, the problem you describe is equivalent to computing the length of the longest increasing subsequence. There's a neat little greedy idea as to why.

Consider the longest increasing subsequence (LIS) of the array. Because the elements are ascending in index and also ascending in value, they must all be in different piles. As a result the minimum number of piles needed is equal to the number of elements in the LIS.

LIS is easily solvable in O(NlogN) using dynamic programming and a binary search.

Note that the algorithm you describe does the same thing as the algorithm below - it finds the first pile you can put the item on (with binary search), or it creates a new pile, so this serves as a "proof" of correctness for your algorithm and a way to reduce your complexity.

Let dp[i] be equal to the minimum value element at the end of an increasing subsequence of length (i + 1). To reframe it in terms of your question, dp[i] would also be equal to the weight of the stone on the ith pile.

from bisect import bisect_left
def lengthOfLIS(nums):

    arr = []

    for i in range(len(nums)):
        idx = bisect_left(arr, nums[i])
        if idx == len(arr):
            arr.append(nums[i])
        else:
            arr[idx] = nums[i]
    return len(arr)