I have some books and a bookshelf. I would like to put as many books on the shelf as possible but I have a rule. All dimensions of the books (height, width and depth) should form a non-increasing sequence on the shelf.
This means every books has to be at least as high as the ones after it on the self. The same goes for the width and depth. You can not rotate the books to swap their height, width and depth.
You should write a program or function which given the dimensions of all the books as input outputs or returns the maximal number of books I can put on the shelf.
Input
- A list of triplets of positive integers where each triplet defines a book's height, width and depth.
- There will be at least one triplet in the input list.
- Two books can have the same lengths along any number of dimensions.
Output
- A single positive integer, the maximal number of books that fit on the shelf obeying the rule.
Time complexity
Your algorithm should have a worst-case time complexity polynomial in the number of books. This means that for example the following time complexities are all valid: O(N^3), O(log(N)*N^2), O(N) and the following ones are invalid: O(2^N), O(N!), O(N^N).
Examples
Input => Output
(1, 1, 1) => 1
(5, 2, 5), (1, 3, 5) => 1
(5, 2, 5), (1, 2, 5) => 2
(2, 2, 2), (2, 2, 2), (2, 2, 2), (1, 3, 6) => 3
(1, 2, 5), (1, 3, 5), (1, 2, 8), (1, 2, 5), (7, 7, 7) => 4
(5, 19, 3), (9, 4, 16), (15, 16, 13), (7, 4, 16), (1, 13, 14), (20, 1, 15), (9, 8, 19), (4, 11, 1) => 3
(1, 1, 18), (1, 13, 7), (14, 1, 17), (8, 15, 16), (18, 8, 12), (8, 8, 15), (10, 1, 14), (18, 4, 6), (10, 4, 11), (17, 14, 17), (7, 10, 10), (19, 16, 17), (13, 19, 2), (16, 8, 13), (14, 6, 12), (18, 12, 3) => 5
This is code golf so the shortest entry wins.
A related interesting book sorting challenge: Book Stack Sort.