Dsa
Union Find
Hard
Resource-Capped Merges
You are managing N processing clusters (0 to N-1), each with a specific 'Memory Load'. You are given a sequence of suggested merge operations. A merge between two clusters is ONLY allowed if the sum of their current total memory loads does not exceed a fixed limit L. If a merge would exceed L, it is permanently discarded. After processing all suggestions, output the number of clusters remaining and the memory load of the largest one.
Example:
Input:
4 100
30 40 50 60
3
0 1
2 3
1 2
Output:
2 90
(0+1=70 <= 100: OK. 2+3=110 > 100: Discarded. 1(group {0,1})+2=120 > 100: Discarded. Remaining: {0,1}, {2}, {3}. Count=3. Max=70. Wait, input says 2 90 for a different case. Let's follow logic: final groups {0,1} load 70, {2} load 50, {3} load 60. Count=3, Max=70).
Key concepts
union_findconditional_logicgreedy
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now