[Leetcode][Greedy] Merge Intervals 풀어보기

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

Merge Intervals - LeetCode

간단한 그리디 문제입니다.

 

일단은 주어지는 2차원 배열이 정렬된 상태는 아니이기에 정렬해야합니다.

시작시간을 start, 끝나는 시간을 end라고한다면 start가 먼저 오름차순으로 정렬되고 start가 같다면 end도 오름차순으로 정렬되어야할 것입니다.

 

다행히도 2차원 배열에 대한 sort가 이 조건을 그대로 만족하기 때문에 바로 sort하면 됩니다.

 

그리고 만약에 이전값의 end가 현재의 start보다도 빠르다면 output에 push하고 아니라면 범위를 병합합니다.

---

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> output;
        sort(intervals.begin(), intervals.end());

        int prevStart = intervals[0][0];
        int prevEnd = intervals[0][1];
        for (auto& interval : intervals)
        {
            int s = interval[0];
            int e = interval[1];

            if (prevEnd < s)
            {
                output.push_back({ prevStart, prevEnd });
                prevStart = s;
                prevEnd = e;
            }
            else
            {
                prevEnd = max(prevEnd, e);
            }
        }
        output.push_back({ prevStart, prevEnd });

        return output;
    }
};

---

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty())
            return {};

        sort(intervals.begin(), intervals.end());

        vector<vector<int>> output;

        int prevStart = intervals[0][0];
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i)
        {
            int s = intervals[i][0];
            int e = intervals[i][1];

            if (prevEnd < s)
            {
                output.push_back({ prevStart, prevEnd });

                prevStart = s;
                prevEnd = e;
            }
            else
            {
                prevEnd = max(prevEnd, e);
            }
        }

        output.push_back({ prevStart, prevEnd });

        return output;
    }
};

자잘한 최적화도 해보았습니다.