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

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

정렬해서 생각해보면 된다.

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		if (intervals.size() == 1) return intervals;
		sort(intervals.begin(), intervals.end());
		vector<vector<int>> mergeV;
		vector<int> v(2);
		mergeV.reserve(intervals.size());
		int mergeIndx = 0;
		int first = intervals[0].at(0);
		int second = intervals[0].at(1);
		int i = 0;
		while (i < intervals.size() - 1)
		{
			if (second >= intervals[i + 1].at(0))
			{
				if (second <= intervals[i + 1].at(1))
				{
					second = intervals[i + 1].at(1);
				}
			}
			else if (second < intervals[i + 1].at(0))
			{
				v[0] = first;
				v[1] = second;
				mergeV.emplace_back(v);
				first = intervals[i + 1].at(0);
				second = intervals[i + 1].at(1);
				
			}
			i++;
			if (i == intervals.size() - 1) //마지막 원소까지 비교해서 넣어줄지 따로구분할지
			{
				if (second >= intervals[i].at(1))
				{
					v[0] = first;
					v[1] = second;
					mergeV.emplace_back(v);
				}
				else
				{
					second = intervals[i].at(1);
					v[0] = first;
					v[1] = second;
					mergeV.emplace_back(v);
				}
			}
		}

		return mergeV;
	}
};

sort 로 O(nlogn), merge 하는데 O(n)

Runtime: 16 ms, faster than 98.73% of C++ online submissions for Merge Intervals.

Memory Usage: 14.3 MB, less than 92.67% of C++ online submissions for Merge Intervals.