엔지니어 게시판
LeetCode 솔루션 분류

[Interview] 56. Merge Intervals

컨텐츠 정보

본문

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

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
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;
    }
};

나무토끼님의 댓글

  • 익명
  • 작성일
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

라플님의 댓글

  • 익명
  • 작성일
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
전체 29 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0