Package g1201_1300.s1203_sort_items_by_groups_respecting_dependencies

Class Solution

java.lang.Object

g1201_1300.s1203_sort_items_by_groups_respecting_dependencies.Solution

public class Solution
extends Object

1203 - Sort Items by Groups Respecting Dependencies.<p>Hard</p> <p>There are <code>n</code> items each belonging to zero or one of <code>m</code> groups where <code>group[i]</code> is the group that the <code>i</code>-th item belongs to and it&rsquo;s equal to <code>-1</code> if the <code>i</code>-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.</p> <p>Return a sorted list of the items such that:</p> <ul> <li>The items that belong to the same group are next to each other in the sorted list.</li> <li>There are some relations between these items where <code>beforeItems[i]</code> is a list containing all the items that should come before the <code>i</code>-th item in the sorted array (to the left of the <code>i</code>-th item).</li> </ul> <p>Return any solution if there is more than one solution and return an <strong>empty list</strong> if there is no solution.</p> <p><strong>Example 1:</strong></p> <p><strong><img src="https://assets.leetcode.com/uploads/2019/09/11/1359_ex1.png" alt="" /></strong></p> <p><strong>Input:</strong> n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]</p> <p><strong>Output:</strong> [6,3,4,1,5,2,0,7]</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]</p> <p><strong>Output:</strong> []</p> <p><strong>Explanation:</strong> This is the same as example 1 except that 4 needs to be before 6 in the sorted list.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= m <= n <= 3 * 10⁴</code></li> <li><code>group.length == beforeItems.length == n</code></li> <li><code>-1 <= group[i] <= m - 1</code></li> <li><code>0 <= beforeItems[i].length <= n - 1</code></li> <li><code>0 <= beforeItems[i][j] <= n - 1</code></li> <li><code>i != beforeItems[i][j]</code></li> <li><code>beforeItems[i]</code>does not contain duplicates elements.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int[]	sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

sortItems

public int[] sortItems(int n,
 int m,
 int[] group,
 List<List<Integer>> beforeItems)