Algorithms, Block Stacking - graph theory

Question

I am struggling with this problem for my algorithms class. Its in graph theory section. I think I am suppose to use maximum weighted matching. But not sure how to construct the bipartite graph. Any suggestions?

We are given n rectangles of sizes a1 × b1, . . . , an × bn. We want to build the highest tower out of the rectangles. In a tower, if a rectangle of width w is on top of a rectangle of width w' then we require w ≤ w' . We are allowed to rotate the rectangles (i. e., an a × b rectangle can be changed into a b × a rectangle). Give an O(n) algorithm which finds the height of the highest possible tower. (For example if the input is 11 × 11, 8 × 2, 1 × 10 then the solution is a tower of height 29 = 11 + 8 + 10.)

Answer 1

If I understand the problem correctly, you can always find the height of the highest possible tower by summing up Math.max(ai,bi). Since you don't need to construct the tower, it is only O(n). Otherwise you need O(nlogn) (sort by height of the rectangles).