Implement minimal-cost overtime/contractor allocation

You must cover H extra engineering hours this week at minimum cost using employee overtime and optional contractors. Each employee i has a maximum overtime cap cap[i] and an overtime cost rate cost_emp[i] per hour. Contractors have unlimited availability at rate cost_contractor per hour. Return both the minimal total cost and an allocation of hours per employee and contractors. Constraints: 0 ≤ hours[i] ≤ cap[i]; sum(hours[i]) + contractor_hours = H. If multiple allocations have the same minimal cost, prefer the one that minimizes contractor_hours; if still tied, minimize the variance of employee overtime hours. Input example: H = 120 cap = [8, 20, 40, 12] cost_emp = [55, 35, 60, 45] cost_contractor = 50 Questions: (a) Describe and implement an O(n log n) algorithm that returns the allocation and total cost. Justify correctness and complexity. (b) Extend your algorithm to handle per-employee overtime tiering (first t[i] hours at rate r1[i], remaining at r2[i] > r1[i]) and a global contractor capacity C. Provide the modified approach and complexity. (c) For the input above, what is the exact optimal allocation and cost?