LeetCode-区間連結クラスの問題

マージ区間
区間の集合を指定します.重複するすべての区間をマージしてください.
例1:入力:[[1,3],[2,6],[8,10],[15,18],出力:[[1,6],[8,10],[15,18]]解釈:区間[1,3]と[2,6]が重なる、それらを[1,6]にまとめる.
分析:C+、並べ替え;区間の左境界に基づいてソートします.現在の区間の右の境界が次の区間の左の境界より大きい場合は、結合します.o(n)の時間的複雑さ.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if (intervals.empty()) return res;
        sort(intervals.begin(), intervals.end(),
            [ ](vector<int> &v1, vector<int> &v2) { return v1[0] < v2[0];});
        
        for (int i = 0; i < intervals.size(); ++i) {
            vector<int> temp = intervals[i];
            while (i + 1 < intervals.size() && temp[1] >= intervals[i+1][0]) {
                ++i;
                temp[1] = max(temp[1], intervals[i][1]);
            }
            res.push_back(temp);
        }
        return res;
    }
};

挿入区間
重複のない区間開始端点に従ってソートされた区間リストが与えられる.リストに新しい区間を挿入するには、リスト内の区間が秩序正しく重複していないことを確認する必要があります(必要であれば、区間をマージできます).
例1:入力:intervals=[[1,3],[6,9]],newInterval=[2,5].出力:[[1,5],[6,9]]
分析1:挿入後にソートし、最初から最後まで連結を巡回します.

class Solution{
public:
	vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
		vector<vector<int>> res;
		intervals.push_back(newInterval);
		if(newInterval.empty())
			return intervals;
		sort(intervals.begin(), intervals.end(),
			[](vector<int> &v1, vector<int> &v2) { return v1[0] < v2[0]; });

		for (int i = 0; i < intervals.size(); ++i) {
			vector<int> temp = intervals[i];
			while (i + 1 < intervals.size() && temp[1] >= intervals[i + 1][0]) {
				++i;
				temp[1] = max(temp[1], intervals[i][1]);
			}
			res.push_back(temp);
		}
		return res;
	}
};

解析2:二分で区間ヘッダの挿入位置を見つけ,合併区間を左右に拡張する.右の状況は複雑で、いくつかの区間を合併する可能性があります.左は前の2点が位置決めされたので、最大左に1つの区間を合併することができます.

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int l = 0, r = intervals.size() - 1, mid;
        //       
        if(r < 0)
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        //     
        while(l < r)
        {
            mid = (l + r) / 2;
            if(intervals[mid][0] < newInterval[0]) l = mid + 1;
            else r = mid;
        }
        //       ，                     
        int x = newInterval[0], y = newInterval[1];
        if(intervals[l][0] > y && (l == 0 || l > 0 && intervals[l - 1][1] < x) || intervals[l][1] < x)
        {
            intervals.push_back({x, y});
            sort(intervals.begin(),intervals.end());
            return intervals;
        }
        //     
        while(r < intervals.size() && intervals[r][0] <= y)
        {
            y = max(y, intervals[r][1]);
            x = min(x, intervals[r][0]);
            r ++;
        }
        //    
        if(l > 0 && intervals[l - 1][1] >= x)
        {
            x = min(x, intervals[l - 1][0]);
            y = max(y, intervals[l - 1][1]);
            l --;
        }
        //          
        intervals.erase(intervals.begin() + l, intervals.begin() + r);
        intervals.push_back({x, y});
        sort(intervals.begin(),intervals.end());
        return intervals;
    }
};