56. Merge Intervals

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

 

2차원 벡터의 각각의 요소의 값이 겹치는 부분이 없도록 병합을 하는 문제.

input 이 몇 개가 들어오는지 명시되어 있지 않다. null 도 입력될 수 있으니 주의한다.

 

Source

입력으로 들어오는 vector의 요소는 순서가 보장되어 있지 않다. 오름 차순 정렬을 하고 overlap 되는 구간을 찾아 병합한다.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        vector<vector<int>> vvi;
        const int size = intervals.size();
        if (size == 0) {
            return vvi;
        }
        sort(intervals.begin(), intervals.end());
        int prevLeft = intervals[0][0];
        int prevRight = intervals[0][1];
        vvi.push_back({ prevLeft, prevRight });
        for (int i = 1; i < size; i++) {

            int cntLeft = intervals[i][0];
            int cntRight = intervals[i][1];

            if (prevRight >= cntLeft) {
                prevLeft = min(cntLeft, prevLeft);
                prevRight = max(cntRight, prevRight);

                if (false == vvi.empty()) {
                    vvi.pop_back();
                }
            }
            else {
                prevLeft = cntLeft;
                prevRight = cntRight;

            }
            vvi.push_back({ prevLeft, prevRight });
        }

        return vvi;
    }
};

24 ms 12.9 mb가 소모 됐다.

 

아래 구문에서 pop_back()을 제거해 보자.

 if (prevRight >= cntLeft) {
 	prevLeft = min(cntLeft, prevLeft);
    prevRight = max(cntRight, prevRight);

	if (false == vvi.empty()) {
		vvi.pop_back();
	}
}

 

20 ms 12.4 mb 큰 차이가 없구먼;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        vector<vector<int>> vvi;
        const int size = intervals.size();
        if (size == 0) {
            return vvi;
        }
        sort(intervals.begin(), intervals.end());
        int prevLeft = intervals[0][0];
        int prevRight = intervals[0][1];
        vvi.push_back({ prevLeft, prevRight });
        for (int i = 1; i < size; i++) {

            int cntLeft = intervals[i][0];
            int cntRight = intervals[i][1];

            if (prevRight >= cntLeft) {
                prevLeft = min(cntLeft, prevLeft);
                prevRight = max(cntRight, prevRight);

                if (false == vvi.empty()) {
                    vvi[vvi.size() - 1][0] = prevLeft;
                    vvi[vvi.size() - 1][1] = prevRight;
                } else {
                    vvi.push_back({ prevLeft, prevRight });
                }
            }
            else {
                prevLeft = cntLeft;
                prevRight = cntRight;
                vvi.push_back({ prevLeft, prevRight });
            }
            
        }

        return vvi;
    }
};