Loading...
Loading...
You are given a list of integers nums and a list of intervals intervals. Each element in intervals contains [left, right] meaning you may swap the elements at any two indices i and j with left <= i, j <= right. Indices start at 0, and both ends of an interval are included.
You may make any number of swaps, in any order, and use each interval as often as you like.
Return the lexicographically smallest array you can reach. An array a is lexicographically smaller than an array b of the same length if, at the first index where they differ, a has the smaller element.
Note that both indices of a swap must lie in one interval. Intervals that only touch, such as [0, 2] and [3, 5], share no index. An index that no interval contains keeps its element.
Input: nums = [5, 3, 4, 1, 2]
intervals = [[0, 2],
[2, 4]]
Output: [1, 2, 3, 4, 5]
Explanation: The two intervals share index 2. The 1 at index 3 can be swapped
to index 2 with the second interval, then to index 0 with the first. In the
same way any element can reach any index, so the whole array can be sorted.
Input: nums = [4, 6, 5, 3, 1, 2]
intervals = [[3, 5],
[0, 2]]
Output: [4, 5, 6, 1, 2, 3]
Explanation: [0, 2] and [3, 5] only touch, so no element can move from one to
the other. The best is to sort indices 0 to 2 and indices 3 to 5 separately.
Input: nums = [9, 7, 8, 1, 0, -2, 5]
intervals = [[1, 2],
[4, 5]]
Output: [9, 7, 8, 1, -2, 0, 5]
Explanation: Indices 0, 3, and 6 are in no interval, so they keep 9, 1, and 5.
Indices 1 and 2 already hold 7, 8 in order. Swapping indices 4 and 5 puts -2
before 0.
Input: nums = [6, 5, 4, 3, 2, 1]
intervals = [[0, 1],
[4, 5],
[1, 4]]
Output: [1, 2, 3, 4, 5, 6]
Explanation: [0, 1] and [4, 5] share no index with each other, but [1, 4]
shares index 1 with the first and index 4 with the second. Together they
connect every index, so the whole array can be sorted.
nums.lengthnums[i] ≤109intervals.length ≤105left ≤ right <n for every [left, right] in intervals