recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
consider a box with n-dimension and there are k different boxes with n dimension each
so the task is simple we have two insert one box into another and we have to find maximum number of boxes which can be inserted one after the another rotation is also allowed around different axis
for example there are 4 box with 2 dimension
so the boxes 1 can be rotated and can be inserted into 3 and 2 can be inserted into 1 so the maximum is 3
i have a question that why topological ordering works here why not normal sorting works what i did was first i sorted all the edges of one boxes in increasing order and then sorted all the boxes in increasing order based on their first index and after that i calculated the longest increasing subsequence
Standard sorting algorithms assume a total ordering: given any two elements, the first is either greater than, equal to, or less than the second. (And this relationship has a few other useful properties, like transitivity.)
However, what you have here is only a partial ordering. Given two boxes, the first might fit into the second, or the second might fit into the first, or they might be the same size…or, neither might fit inside the other. (10, 1) and (2, 5) fall into this last category.
Standard sorting algorithms will choke on this. But topological sorting only needs a partial ordering, and is also more efficient (running in linear time instead of linearithmic). So it's the right tool for the job here.