Minimum Cost to Build a Skilled Team
You are given candidates who can be hired for a project. Each candidate has a hiring cost and may be skilled in Java, Python, both languages, or neither language.
Skill Representation
"00" means the candidate knows neither Java nor Python."01" means the candidate knows only Python."10" means the candidate knows only Java."11" means the candidate knows both Java and Python.
Team Requirements
A team is k-skilled when at least k selected candidates know Java and at least k selected candidates know Python. A candidate with skill code "11" contributes to both requirements.
For every value of k from 1 to the number of candidates, find the minimum total hiring cost of a k-skilled team. Use -1 when such a team cannot be formed.
Method Signature
List<Long> findMinimumHiringCosts( List<Integer> hiringCost, List<String> skills )
Parameters
hiringCost contains the cost of hiring each candidate.skills contains the two-character skill code of each corresponding candidate.
Returns
Return a list containing one result for every k from 1 to n. The value at index k - 1 must be the minimum cost of a k-skilled team, or -1 if no such team exists.
Constraints
1 ≤ n ≤ 200,000hiringCost.size() = skills.size() = n1 ≤ hiringCost[i] ≤ 1,000,000,000skills[i] is one of "00", "01", "10", or "11".- Results are returned in increasing order of
k, from 1 through n.
Examples
Example 1
findMinimumHiringCosts( hiringCost = List.of(5, 2, 8, 4, 7), skills = List.of("10", "01", "11", "01", "10") )
Output: List.of(7L, 15L, 26L, -1L, -1L)
For k = 1, select the Java-only candidate costing 5 and the Python-only candidate costing 2, for a total cost of 7.
For k = 2, additionally select the candidate skilled in both languages costing 8, for a total cost of 15.
For k = 3, all five candidates having at least one required skill must be selected, for a total cost of 26. A team cannot be formed for k = 4 or k = 5.
Example 2
findMinimumHiringCosts( hiringCost = List.of(6, 1, 3, 10), skills = List.of("11", "11", "00", "10") )
Output: List.of(1L, 7L, -1L, -1L)
The two candidates skilled in both languages cost 1 and 6. Therefore, the minimum costs for k = 1 and k = 2 are 1 and 7. No team can satisfy the Python requirement for larger values of k.