Maximize Happiness

Problem Overview

• Select employees within a budget and a manager (may be outside the hired set) who can assign tasks via the RM chain, maximizing happiness = manager leadership × hires.
• Input: T test cases; for each, N and budget M; for i=1..N: RM R[i] (0<=R[i]<i), cost C[i], leadership L[i].
• Output: maximum happiness for each test case.
• Constraints: T≤10, N≤1e5, M≤1e9; 1≤C[i]≤M; 1≤L[i]≤1e9.
• Context: outsourcing company hierarchy; asked in Rubrik interviews; a coding interview problem and interview question.