FastPrepFastPrep
Problem Brief

Chain Merge

INTERNOA

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'.

    1Example 1

    Input
    n = 3, retentionTimes = [[3, 4, 5, 8], [3, 2, 3, 1], [3, 6, 7, 9]]
    Output
    [3, 1, 2]
    Explanation
    n/a

    Constraints

    Limits and guarantees your solution can rely on.

  • 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
    • public int[] chainMerge(int n, int[][] retentionTimes) {
  // write your code here
}
    Input

    n

    3

    retentionTimes

    [[3, 4, 5, 8], [3, 2, 3, 1], [3, 6, 7, 9]]

    Output

    [3, 1, 2]

    Sign in to submit your solution.