LeetCode 57 Insert Interval

概述

https://leetcode.com/problems/insert-interval/

分类讨论法

注意处理遍历结束后也没插进入的情况。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        int a = newInterval[0], b = newInterval[1];
        bool inserted = false;
        bool inserting = false;
        for (int i = 0; i < intervals.size(); i ++) {
            if (inserting) {
                if (b < intervals[i][0]) {
                    ans.push_back({a, b});
                    ans.push_back(intervals[i]);
                    inserted = true;
                    inserting = false;
                } else if (b <= intervals[i][1]) {
                    ans.push_back({a, intervals[i][1]});
                    inserted = true;
                    inserting = false;
                } else {
                    continue;
                }
            } else {
                if (inserted || a > intervals[i][1]) {
                    ans.push_back(intervals[i]);
                } else {
                    // a <= intervals[i][1]
                    if (b < intervals[i][0]) {
                        ans.push_back(newInterval);
                        ans.push_back(intervals[i]);
                        inserted = true;
                    } else if (b <= intervals[i][1]) {
                        ans.push_back({min(a, intervals[i][0]), intervals[i][1]});
                        inserted = true;
                    } else {
                        // b > intervals[i][1]
                        a = min(a, intervals[i][0]);
                        inserting = true;
                    }
                }
            }
        }
        if (!inserted) {
            ans.push_back({a, b});
        }
        return ans;
    }
};

Links: leetcode-57-insert-interval

未经允许，禁止转载，本文源站链接：https://iamazing.cn/