Energy Crisis

Problem Overview

• Determine if energy levels can be assigned to a connected, undirected graph so that on every edge the endpoints’ energies differ by exactly 1, matching known eclipse directions.
• Input: n planets, m pathways, with some edges having fixed direction of “who eclipses whom”; output the maximum stellar gradient (min energy − max energy) or −1 if impossible. Constraints: 1≤n≤200, 1≤m≤2000.
• Context: models an interstellar civilisation’s alliances.
• Source: Rubrik interviews; a classic coding interview problem and interview question.