Greedy Algorithms8 sections · 316 units
Open in Course

Class Photos - Greedy Solution

Match by rank

Greedy approach:

1.1. Sort both classes by height.

2.2. Determine which class goes in front (the one with the shorter tallest student).

3.3. Compare position by position: each back-row student must be strictly taller than the corresponding front-row student. If all comparisons pass, return true. Otherwise, false. It works because if tallest of class A < tallest of class B, then class A must be in front. And sorted order maximizes the chance of success at each position. Time: O(nlogn)O(n \log n). Space: O(1)O(1).