update box stacking problem but all the height are same

user_16444134 0
Viewed 186

The Box Stacking Statement: Given n rectangle boxes, that the i box has height h[i], width w[i] and depth d[i]. Create a stack of boxes that is the tallest one possible, but only can stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

But in this problem, all the boxes are has the same height (h[1]=h[2]=...h[n]) and N <= 100000. And we don't need to rotate the boxes anymore.

Example:

n = 5
w[]={1,3,5,7,9}; d[]={5,7,4,6,8}

The answer is: 3 ( [1x5] ; [3x7] ; [9x8] )

I only can solve it in O(n^2) but I need less than it (can be O(n) or O(nlogn)).

lis dynamic-programming
1 Answers

You can't solve it with O(n), because otherwise you would have an algorithm to sort n numbers in O(n).

But you could solve it with O(n log n).

  1. First you need to sort with w's in ascending order. If you have two w's that are equals, sort in descending order by their d's.
  2. Second you need to solve a LIS problem in the list of d's, and you will have you longest stack.

Please note that there are several approaches for LIS as far as I know, the DP approach is O(n^2), but there are a O(n log n) approach which you can find one implementation and explanation(which I used) on GFG.

Here is my implementation of your problem with Kotlin:

companion object {
    @JvmStatic
    fun main(args: Array<String>) {
        println(
            maxTower(
                arrayOf(
                    intArrayOf(5, 4),
                    intArrayOf(6, 4),
                    intArrayOf(6, 7),
                    intArrayOf(2, 3),
                    intArrayOf(1, 1),
                    intArrayOf(2, 5),
                    intArrayOf(3, 5),
                    intArrayOf(3, 4),
                    intArrayOf(4, 4),
                    intArrayOf(4, 5)
                )
            )
        )
    }

    fun maxTower(blocks: Array<IntArray>): Int {
        if (blocks.isEmpty()) return 0
        blocks.sortWith(Comparator { o1, o2 ->
            if (o1[0] == o2[0]) {
                o2[1] - o1[1]
            } else {
                o1[0] - o2[0]
            }
        })
        val map = blocks.map { it[1] }
        return LIS(map)
    }

    fun ceilIndex(A: IntArray, l: Int, r: Int, key: Int): Int {
        var l = l
        var r = r
        while (r - l > 1) {
            val m = l + (r - l) / 2
            if (A[m] >= key) r = m else l = m
        }
        return r
    }

    fun LIS(A: List<Int>): Int {
        val size = A.size
        val tailTable = IntArray(size)
        tailTable[0] = A[0]
        var len = 1
        for (i in 1 until size) {
            if (A[i] < tailTable[0])
                tailTable[0] = A[i] else if (A[i] > tailTable[len - 1])
                tailTable[len++] = A[i]
            else
                tailTable[ceilIndex(tailTable, -1, len - 1, A[i])] = A[i]
        }
        return len
    }
}
user_4826820
Related