Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Queue Reconstruction by Height

People in line

You have a queue of people with attributes (h,k)(h, k) where hh is height and kk is the number of people in front who are taller or equal height. Reconstruct the queue.

For example, [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]][[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] becomes [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]][[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]. The order you insert people matters.

Think about which people are easiest to place correctly. Greedy insight: tallest people have the simplest constraints because no one shorter affects them.