티스토리 뷰
Algorithm/LeetCode Daily Challenge
[LeetCode - Daily Challenge] 56. Merge Intervals
Jaime.Lee 2021. 12. 25. 10:30728x90
반응형
Problem
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^4
Solution
시작과 끝 인덱스를 가진 배열이 존재할 때 중복되는 부분을 모두 합친 배열을 반환하는 문제입니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0 || intervals.length == 1) {
return intervals;
}
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0])); // (1)
List<int[]> list = new ArrayList<>();
int[] interval = intervals[0]; // (2)
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= interval[1]) { // (3)
interval[1] = Math.max(intervals[i][1], interval[1]);
} else { // (4)
list.add(interval);
interval = intervals[i];
}
}
list.add(interval);
int[][] result = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
- 시작을 기준으로 정렬해줍니다.
- 비교할 기준을 지정합니다.
- 기준의 끝이 다음 interval의 시작보다 큰 경우, 현재 끝 값과 비교 대상의 끝 값중 더 큰 값으로 끝 값을 갱신합니다.
- 기준의 끝이 다음 interval의 시작보다 작은 경우 기존 interval을 결과에 추가하고 기준 값을 갱신합니다.
Test
package io.lcalmsky.leetcode.merge_intervals;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import java.util.Arrays;
import org.junit.jupiter.api.Test;
class SolutionTest {
@Test
void givenTwoDimensionArray_whenMergeIntervals_thenCorrect() {
assertAll(
() -> test(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}},
new int[][]{{1, 6}, {8, 10}, {15, 18}}),
() -> test(new int[][]{{1, 4}, {4, 5}}, new int[][]{{1, 5}}),
() -> test(new int[][]{}, new int[][]{})
);
}
public void test(int[][] given, int[][] expected) {
// when
Solution mergeIntervals = new Solution();
int[][] result = mergeIntervals.merge(given);
System.out.println(Arrays.deepToString(result));
// then
assertArrayEquals(expected, result);
}
}
728x90
반응형
'Algorithm > LeetCode Daily Challenge' 카테고리의 다른 글
[LeetCode - Daily Challenge] 973. K Closest Points to Origin (0) | 2021.12.28 |
---|---|
[LeetCode - Daily Challenge] 227. Basic Calculator II (0) | 2021.12.26 |
[LeetCode - Daily Challenge] 56. Merge Intervals (0) | 2021.12.25 |
[LeetCode - Daily Challenge] 210. Course Schedule II (0) | 2021.12.24 |
[LeetCode - Daily Challenge]143. Reorder List (0) | 2021.12.22 |
[LeetCode - Daily Challenge] 1200. Minimum Absolute Difference (0) | 2021.12.21 |
댓글
공지사항
- Total
- 71,750
- Today
- 113
- Yesterday
- 133
링크
TAG
- Linux
- 스프링 부트
- QueryDSL
- 스프링 부트 회원 가입
- Spring Boot
- Jackson
- 스프링부트
- JSON
- 스프링 부트 애플리케이션
- 알고리즘
- 스프링 데이터 jpa
- leetcode
- 스프링 부트 jwt
- gRPC
- r
- leetcode binary search
- spring boot application
- Java
- intellij
- spring boot app
- 스프링 부트 웹 애플리케이션
- Spring Data JPA
- JPA
- spring boot jwt
- Spring Boot Tutorial
- leetcode stack
- proto3
- 도메인 설계
- leetcode bst
- 스프링 부트 튜토리얼