LeetCode 57. 挿入区間

構想:この問題には良い構想はなく、論理推理を強行して様々な可能性をリストした.一時的なvectorを使用して、挿入する必要がある区間の左右の端点値を記録し、元の区間リストを巡り、一つ一つ判断します.同時に、flagを使用して、この挿入が必要な区間が挿入されたかどうかを記録します.1、挿入が必要な区間が挿入されているか、挿入が必要な区間が現在の区間の右側にある場合は、現在の区間を戻りリストに挿入する脳がない.2、まだ挿入されていない場合は、現在の区間と挿入が必要な空間の関係を判断する必要があります.

挿入される区間の右端が現在の区間の左端より小さい場合は、挿入される空間を戻りリストに挿入し、現在の区間も挿入し、flagをtrueに設定します.

挿入される区間の右端点が現在の区間の右端点以下である場合、区間をマージし、マージの結果を追加する必要があります.(集計ルール、左が小さい人、右が現在の区間の右端を取ればよい)

上面が満たされておらず、挿入される区間の左端点が現在の区間の右端点以下、すなわち左に交差がある場合、この場合、挿入対象区間の左端点(左の方が小さい方)を更新する必要があります.この場合は追加できません.挿入対象区間の右端点後の区間の関係が分からないため(あれば)、挿入対象区間

のみを更新します.
3、ループ終了後、挿入待ち区間が完了したか否かを判断し、まだ挿入されていない場合は、この挿入待ち区間を戻りリストに加算する
コード#コード#

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int len = intervals.size();
        vector<vector<int>> res;
        if(len == 0)
        {
            res.push_back(newInterval);
            return res;
        }
        bool haveHandled = false;
        vector<int> tempVec = newInterval;
        for(int i = 0;i < len;++i)
        {
            if(haveHandled || tempVec[0] > intervals[i][1])//                  
                res.push_back(intervals[i]);
            else
            {
                //                 ，            
                if(tempVec[1] < intervals[i][0])
                {
                    haveHandled = true;
                    res.push_back(tempVec);
                    res.push_back(intervals[i]);
                }
                else if(tempVec[1] <= intervals[i][1])//                     
                {
                    haveHandled = true;
                    tempVec[0] = tempVec[0] < intervals[i][0]?tempVec[0]:intervals[i][0];
                    tempVec[1] = intervals[i][1];
                    res.push_back(tempVec);
                }
                else if(tempVec[0] <= intervals[i][1])//                 ,             
                    tempVec[0] = tempVec[0] < intervals[i][0]?tempVec[0]:intervals[i][0];
            }
        }
        if(haveHandled == false)
            res.push_back(tempVec);
        return res;
    }
};

テーマと出所

         ，               。

            ，                   （       ，      ）。

   1:

  : intervals = [[1,3],[6,9]], newInterval = [2,5]
  : [[1,5],[6,9]]
   2:

  : intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
  : [[1,2],[3,10],[12,16]]
  :          [4,8]   [3,5],[6,7],[8,10]   。

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/insert-interval
          。           ，          。