LeetCode 솔루션 분류
[Interview] 56. Merge Intervals
본문
56. Merge Intervals
Medium
13381518Add to ListShareGiven 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
관련자료
댓글 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.
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
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
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