FastPrepMaximize Happiness

Maximize Happiness

Rubrik logoRubrik● HardOA
Learn

Problem statement

Employees form a rooted company tree. Row i of employeeData is [manager, cost, leadership] for employee i + 1. Manager 0 marks the root.

Choose one employee as the manager for a client, then hire any subset of employees in that manager's subtree. The chosen manager may be hired, but does not have to be. The total hiring cost must not exceed budget.

The client's happiness is:

chosen manager's leadership * number of hired employees.

Return the maximum possible happiness.

Function

maximizeHappiness(employeeData: int[][], budget: int) → long

Examples

Example 1

employeeData = [[0, 10, 400], [1, 10, 300], [2, 15, 100], [1, 10, 60], [1, 15, 800], [2, 5, 100], [2, 5, 100]]budget = 20return = 1200

Choose employee 1 as manager and hire employees 2, 6, 7. Their total cost is 20, so happiness is 400 * 3 = 1200.

Constraints

  • 1 <= T <= 10
  • 1 <= N <=100 000 The number of Employees
  • 1 <= M <=1 000 000 000 The budget
  • 0 <= R[i] < i The RM for each employee
  • 1 <= C[i] <= M The amount of cost of each employee
  • 1 <= L[i] <= 1 000 000 000 The leadership level of each employee
  • Subtask 1: N <= 10
  • Subtask 2: N <= 3000
  • Subtask 3: Original

More Rubrik problems

See Rubrik hiring insights
public long maximizeHappiness(int[][] employeeData, int budget) {
  // write your code here
}
employeeData[[0, 10, 400], [1, 10, 300], [2, 15, 100], [1, 10, 60], [1, 15, 800], [2, 5, 100], [2, 5, 100]]
budget20
expected1200
Checking account…