🥈

Merge Intervals

Created

2021/12/24 02:46

문제 번호

카테고리

Array

Sorting

Merge Intervals - LeetCode

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

https://leetcode.com/problems/merge-intervals/

Code

제출 날짜	시간	메모리
2021/12/24	4 ms	4.5 MB

// 56. Merge Intervals
//
// https://leetcode.com/problems/merge-intervals/

// sort package imported to order the interval slices
import (
	"sort"
)

// merge function literally merge the intervals.
// [[1, 3], [2, 6], [8, 10], [15, 18]] will be [[1, 6], [8, 10], [15, 18]].
// To merge, compare the start and the end should be easy. Sorting with the start point is necessary.
// After that, just compare the following if statement and update.
// No need to use a new [][]int, but adopted the way to make the code clear.
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	res := [][]int{}
	for i, interval := range intervals {
		if i == 0 {
			res = append(res, interval)
			continue
		}
		temp := res[len(res)-1]
		if temp[1] >= interval[0] && temp[1] < interval[1] {
			res[len(res)-1] = []int{temp[0], interval[1]}
		} else if temp[1] < interval[0] {
			res = append(res, interval)
		}
	}
	return res
}
Go
복사