LeetCode 솔루션

[Interview] 56. Merge Intervals

Jack 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.05 21:37

4,271 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

56. Merge Intervals

Medium

13381518Add to ListShare

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 <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

#leetcode, #문제풀이, #시즌3, #medium, #facebook, #amazon, #google, #bloomberg, #saleforce, #apple, #microsoft, #uber, #adobe, #ibm, #linkedin, #vmware, #snapchat, #walmart global tech, #oracle, #yandex, #tiktok, #shopee, #twitter, #bytedance, #cisco, #intuit, #nvidia, #morgan stanley, #array, #sorting

익명
작성일 2022.05.05 22:23

C++
Runtime: 196 ms, faster than 8.61% of C++ online submissions for Merge Intervals.
Memory Usage: 47.2 MB, less than 5.42% of C++ online submissions for Merge Intervals.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        
        sort(intervals.begin(), intervals.end(), [&](const vector<int> a, const vector<int> b) {
            return a[0] < b[0];
        });
        
        vector<vector<int>> res;
        vector<int> curr(intervals[0]);
        
        for (int i = 1; i < n; ++i) {
            if (curr[1] >= intervals[i][0]) {
                curr[1] = max(curr[1], intervals[i][1]);
            }
            else {
                res.push_back(curr);
                curr = intervals[i];
            }
        }
        res.push_back(curr);
        return res;
    }
};

익명
작성일 2022.05.06 11:05

Runtime: 161 ms
Memory Usage: 18.1 MB

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        pointer, pointer2 = 0, 1
        while pointer < len(intervals) and pointer2 < len(intervals):
            # 1, 3 / 1, 4
            if intervals[pointer][0] == intervals[pointer2][0]:
                intervals[pointer][1] = intervals[pointer2][1]
                del intervals[pointer2]
            # 1, 4 / 3, 5
            elif intervals[pointer][1] >= intervals[pointer2][0]:
                # 1, 6 / 3, 5
                if intervals[pointer][1] >= intervals[pointer2][1]:
                    del intervals[pointer2]
                # 1, 4 / 3, 5
                else:
                    intervals[pointer][1] = intervals[pointer2][1]
                    del intervals[pointer2]
            # 1, 2 / 3, 4
            else:
                pointer += 1
                pointer2 += 1
        return intervals

익명
작성일 2022.05.08 01:47

Python3
Runtime: 159 ms, faster than 76.19% of Python3 online submissions for Merge Intervals.
Memory Usage: 18 MB, less than 85.50% of Python3 online submissions for Merge Intervals.

intervals.sort()
if len(intervals) <2:
return intervals

fir = intervals[0]
result = []
for inter in intervals:
if inter[0] > fir[1]:
result.append(fir)
fir = inter
else:
fir[1] = max(fir[1], inter[1])
result.append(fir)
return result