Chain Merge
Rubrik● MediumINTERNOAProblem statement
You are given a system that consists of n chains ( C_1, C_2, ..., C_n ). Each chain consists of a sequence of blobs where each blob has a dependency on its parent blob. Each blob of chain ( C_i ) has a corresponding retention time ( B_(i,j) ), where 1<=j<=m_i and m_i is the number of blobs in chain ( i ).
A blob can only be removed from the system if the following conditions are met:
- Its retention time has passed.
- None of the other blobs are dependent on it.
The admin has decided to organize the system better by merging these chains into a larger, single chain. This is accomplished by introducing dependencies between the first blobs of each chain.
Assume there were 3 chains:
Some of the possibilities for merging the chains:
In the merged structure, no blob's removal should get delayed due to the restructuring. Help admin achieve this by choosing the correct order of links between the chains.
Input Format
N -> number of chains.
N lines of the form
c = Chain length
c space separated integers = retention times of blobs
where blob at index 'i' is parent of blob at index 'i+1'.
Output format
Array of integers representing the dependency order of the first blobs of the chains.
(A dependency is added from blob at index 'i' to blob at index 'i+1'.
Function
chainMerge(n: int, retentionTimes: int[][]) → int[]Examples
Example 1
n = 3retentionTimes = [[3, 4, 5, 8], [3, 2, 3, 1], [3, 6, 7, 9]]return = [3, 1, 2]n/a
Constraints
- All blobs across the system have a unique retention time.
- Number of chains(
n) <= 1e5, blobs per chain (m_i)<=1e5 - It's guaranteed that total number of blobs in the system <= 3e6