๋์ด๋: Medium
ํค์๋: Array
๋ฌธ์
๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/merge-intervals/description/
์ฃผ์ด์ง ๊ฐ๊ฒฉ ๋ฐฐ์ด์์, intervals[i] = [starti, endi]์ธ ๊ฐ๊ฒฉ๋ค์ด ์์ ๋, ๊ฒน์น๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ๋ณํฉํ๊ณ , ์
๋ ฅ๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ํฌ๊ดํ๋ ๊ฒน์น์ง ์๋ ๊ฐ๊ฒฉ๋ค์ ๋ฐฐ์ด์ ๋ฐํํ์์ค.
๋ฌธ์ ํ์ด
๊ฒน์น๋ ๊ตฌ๊ฐ๋ค์ ํฉ์ณ์ฃผ๊ธฐ์ํด์, intervals ๋ฅผ start time ๊ธฐ์ค์ผ๋ก sortingํ๊ณ merge๋ฅผ ์งํํ๋ค. ๊ทธ๋ฌ๋ฉด sort๋ O(n log n)์ด ๋ณด์ฅ๋๊ณ , sorting ๋ array์ ๋ํด์ merge๋ง ํด์ฃผ๋ฉด ๋๋ฏ๋ก O(n). ์ต์ข
์ ์ผ๋ก O(n log n) ๋ณต์ก๋๋ก ํด๊ฒฐ.
#include <algorithm>
#include <vector>
using namespace std;
bool compare(const vector<int>& left, const vector<int>& right){
return left[0] < right[0];
};
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), compare);
vector<vector<int>> ans;
for(auto interval: intervals){
if(ans.size() > 0 && interval[0] <= ans[ans.size()-1][1]){
ans[ans.size()-1][1] = max(interval[1], ans[ans.size()-1][1]);
} else {
ans.emplace_back(interval);
}
}
return ans;
}
};