Construct Maximum Balanced Circle

Problem Overview

• Choose the largest subset of n people (heights a[i]) and arrange them in a circle where every adjacent pair, including first–last, differs in height by at most 1.
• Input: n (1≤n≤2·10^5) and heights (1≤a[i]≤2·10^5). Output: k and a circular list of k heights meeting the rule.
• Context: arranging people by similar heights in a balanced circle for seating/grouping.
• Asked in Microsoft interviews; a coding interview problem and common interview question.