Skyscraper

Skyscraper — a Microsoft interviews coding interview problem. Given an array A of N maximum heights, pick actual positive heights B[0..N-1] so that each B[k] <= A[k], all heights are distinct, and the total sum is maximized. Return any valid B. This interview question uses large N and values, and guarantees a solution.