You are given an array of intervals
, where intervals[i]
= [start
, end
] and each start
is unique.
The right interval for an interval i
is an interval j
such that start
>= end
and start
is minimized. Note that i
may equal j
.
Return an array of right interval indices for each interval i
. If no right interval exists for interval i
, then put -1
at index i
.
Input | Output |
---|---|
intervals = [[1,2]] | [-1] |
There is only one interval in the collection, so it outputs -1.
Input | Output |
---|---|
intervals = [[3,4],[2,3],[1,2]] | [-1,0,1] |
There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start
= 3 is the smallest start
that is >= end
= 3. The right interval for [1,2] is [2,3] since start
= 2 is the smallest start
that is >= end
= 2.
Input | Output |
---|---|
intervals = [[1,4],[2,3],[3,4]] | [-1,2,-1] |
There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start
= 3 is the smallest start
that is >= end
= 3.
์ด ๋ฌธ์ ๋ ์์์ ๊ณผ ๋์ ์ผ๋ก ์ด๋ฃจ์ด์ง ์ฌ๋ฌ ๊ฐ์ ๊ตฌ๊ฐ ์ค์์, ๊ฐ ๊ตฌ๊ฐ์ ๋์ ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ์์์ ์ ๊ฐ์ง ๊ตฌ๊ฐ์ ์ฐพ๋ ๊ฒ์ด๋ค. ๋จ, ๋ง์ฝ ๊ทธ๋ฐ ๊ตฌ๊ฐ์ด ์๋ค๋ฉด -1์ ๋ฐํํด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด, ๊ตฌ๊ฐ ๋ฐฐ์ด์ด ๋ค์๊ณผ ๊ฐ๋ค๊ณ ๊ฐ์ ํด๋ณด์
intervals = [[1, 2], [2, 3], [0, 1]]
์ด ๋ฐฐ์ด์ ์ ๊ฐ ๊ตฌ๊ฐ์ ์ดํด๋ณด๋ฉด
๋์ ์ด 2์ด๊ธฐ ๋๋ฌธ์, ์์์ ์ด 2 ์ด์์ธ ๊ตฌ๊ฐ์ ์ฐพ์์ผ ํ๋ค.
์ฌ๊ธฐ์๋ ๋ ๋ฒ์งธ ๊ตฌ๊ฐ [2, 3]์ด ํด๋น๋๋ค.
๋ฐ๋ผ์ ์ธ๋ฑ์ค 1์ ๋ฐํํ๋ค.
๋์ ์ด 3์ด๊ธฐ ๋๋ฌธ์, ์์์ ์ด 3 ์ด์์ธ ๊ตฌ๊ฐ์ ์ฐพ์์ผ ํ๋ค.
ํ์ง๋ง ์ฃผ์ด์ง ๊ตฌ๊ฐ ์ค์์๋ ๊ทธ๋ฐ ๊ตฌ๊ฐ์ด ์๋ค.
๋ฐ๋ผ์ -1์ ๋ฐํํ๋ค.
๋์ ์ด 1์ด๊ธฐ ๋๋ฌธ์, ์์์ ์ด 1 ์ด์์ธ ๊ตฌ๊ฐ์ ์ฐพ์์ผ ํ๋ค.
์ฌ๊ธฐ์๋ ์ฒซ ๋ฒ์งธ ๊ตฌ๊ฐ [1, 2]๊ฐ ํด๋น๋๋ค.
๋ฐ๋ผ์ ์ธ๋ฑ์ค 0์ ๋ฐํํ๋ค.
์ด ๋ชจ๋ ๊ฒ์ ์ข ํฉํ๋ฉด, ๊ฐ ๊ตฌ๊ฐ์ ๋ํ ๊ฒฐ๊ณผ๋ ๋ค์๊ณผ ๊ฐ๋ค.
๋ฐ๋ผ์ ์ต์ข
์ ์ผ๋ก ๋ฐํ๋๋ ๋ฐฐ์ด์ [1, -1, 0]
์ด ๋๋ค.
์ด์ง ํ์์ ๋ํ ๊ฐ๋ ์ ๋ฐ๋ก ์ฐพ์์ ์ ๋ฆฌ๋ฅผ ํด ๋ณด์๋ค.
// intervals ์์ : [[3,4], [2,3], [1,2]]
class Solution {
public int[] findRightInterval(int[][] intervals) {
int[] answer = new int[intervals.length];
HashMap<Integer, Integer> startIndexMap = new HashMap<>();
// ์์์ ๊ณผ ์ธ๋ฑ์ค๋ฅผ ๋งคํํ์ฌ ์ ์ฅ
for (int i = 0; i < intervals.length; i++) {
startIndexMap.put(intervals[i][0], i);
}
// startIndexMap
// Key -> Value
// 3 -> 0
// 2 -> 1
// 1 -> 2
// ์์์ ๋ฐฐ์ด์ ์ ๋ ฌ
int[][] sortedIntervals = new int[intervals.length][2];
for (int i = 0; i < intervals.length; i++) {
sortedIntervals[i] = intervals[i];
}
Arrays.sort(sortedIntervals, (a, b) -> Integer.compare(a[0], b[0]));
// sortedIntervals
// [[1,2], [2,3], [3,4]]
// ๊ฐ ๊ตฌ๊ฐ์ ๋์ ์ ๋ํด ์ด์ง ํ์
for (int i = 0; i < intervals.length; i++) {
int end = intervals[i][1];
int index = binarySearch(sortedIntervals, end);
if (index == -1) {
answer[i] = -1;
}
else {
answer[i] = startIndexMap.get(sortedIntervals[index][0]);
}
}
return answer;
}
// ์ด์ง ํ์
public int binarySearch(int[][] intervals, int target) {
int left = 0;
int right = intervals.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (intervals[mid][0] >= target) {
result = mid; // ๊ฐ๋ฅํ ์ธ๋ฑ์ค ์ ์ฅ
right = mid - 1; // ๋ ์์ ์ธ๋ฑ์ค๋ฅผ ์ฐพ๊ธฐ ์ํด ์ผ์ชฝ์ผ๋ก ์ด๋
}
else {
left = mid + 1; // ๋ ํฐ ์ธ๋ฑ์ค๋ฅผ ์ฐพ๊ธฐ ์ํด ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋
}
}
return result;
}
}
startIndexMap
์ ์ฌ์ฉํ์ฌ ๊ฐ ์์์ ๊ณผ ๊ทธ์ ํด๋นํ๋ ์ธ๋ฑ์ค๋ฅผ ์ ์ฅํ๋ค.sortedIntervals
๋ฐฐ์ด์ ์์์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ค.
๋ด์ฉ์ด ์์ฐจ๊ณ ๊น๋ํ TIL ์ ๋ณด๊ณ ๊ฐ๋๋ท..!