Python/JS/Go/C++ O( n ) by boundary checking [w/ Comment] 有中文解題文章
\u4E2D\u6587\u89E3\u984C\u6587\u7AE0\n\nPython O( n ) by boundary checking\n\n---\n\nImplementation:\n\nPython:\n\n\nclass Solution:\n    def insert(self, inter
[\u4E2D\u6587\u89E3\u984C\u6587\u7AE0](https://vocus.cc/article/65f68ee8fd897800013d1605)\n\nPython O( n ) by boundary checking\n\n---\n\n**Implementation**:\n\nPython:\n\n```\nclass Solution:\n    def insert(self, intervals, newInterval):\n        \n        # Constant to help us access start point and end point of interval\n        START, END = 0, 1\n        \n        s, e = newInterval[START], newInterval[END]\n        \n        left, right = [], []\n        \n        for cur_interval in intervals:\n            \n            if cur_interval[END] < s:\n                # current interval is on the left-hand side of newInterval\n                left += [ cur_interval ]\n                \n            elif cur_interval[START] > e:\n                # current interval is on the right-hand side of newInterval\n                right += [ cur_interval ]\n                \n            else:\n                # current interval has overlap with newInterval\n                # merge and update boundary\n                s = min(s, cur_interval[START])\n                e = max(e, cur_interval[END])\n                \n        return left + [ [s, e] ] + right    \n```\n\n---\n\nJavascript:\n\n```\nvar insert = function(intervals, newInterval) {\n    \n    const [START, END] = [0, 1];\n    \n    // start point as well as end point of new interval\n    let [s, e] = [ newInterval[START], newInterval[END] ];\n    \n    // left: \u3000record of intervals on left hand side\n    // right:\u3000record of intervals on right hand side\n    let [left, right] = [ [], [] ];\n    \n    for( let curInterval of intervals){\n        \n        if( curInterval[END] < s ){\n            \n            // current interval is on the left hand side of newInterval\n            left.push( curInterval);\n            \n        }else if( curInterval[START] > e ){\n            \n            // current interval is on the right hand side of newInterval\n            right.push( curInterval );\n        }else{\n            \n            // current interval has overlap with newInterval\n            // merge and update boundary\n            s = Math.min( s, curInterval[START] );\n            e = Math.max( e, curInterval[END] );\n            \n        }\n        \n    }\n    \n    let result = left.concat( [ [s, e] ]).concat(right);\n    return result;\n    \n};\n```\n\n---\n\nGo:\n\n\n```\n// native Go doesn\'t have built-in interger min/max library function\n// we have to make it manually\n\nfunc max(x, y int) int{\n    if x >= y {\n        return x\n    }else{\n        return y\n    }\n}\n\nfunc min(x, y int) int{\n    if x <= y{\n        return x\n    }else{\n        return y\n    }\n}\n\n// ---------------------------------\n\n\nfunc insert(intervals [][]int, newInterval []int) [][]int {\n    \n    // Constant to help us access start point and end point of interval\n    const START, END = 0, 1\n    \n    s := newInterval[START]\n    e := newInterval[END]\n    \n    left := make( [][]int, 0)\n    right := make( [][]int, 0)\n    \n    for _, curInterval := range intervals{\n        \n        if curInterval[END] < s{\n            \n            // current interval is on the left hand side of newInterval\n            left = append(left, curInterval)\n            \n        }else if curInterval[START] > e{\n            \n            // current interval is on the right hand side of newInterval\n            right = append(right, curInterval)\n            \n        }else{\n            \n            // current interval has overlap with newInterval\n            // merge and update boundary\n            s = min( s, curInterval[START] )\n            e = max( e, curInterval[END] )\n            \n        }\n    }\n    \n    result := make( [][]int, 0)\n    result = append(result, left...)\n    result = append(result, []int{s, e} )\n    result = append(result, right...)\n    \n    return result\n    \n}\n```\n\n---\n\nC++:\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        \n        // Constant to help us access start point and end point of interval\n        const int START=0, END=1;\n        \n        int s=newInterval[START], e=newInterval[END];\n        \n        vector< vector<int> > left, right;\n        \n        for( auto& curInterval : intervals ) {\n            \n            if (curInterval[END] < s){\n                \n                // current interval is on the left hand side of newInterval\n                left.push_back( curInterval );\n                \n            }else if( curInterval[START] > e ){\n                \n                // current interval is on the right hand side of newInterval\n                right.push_back( curInterval );\n            \n            }else{\n                // current interval has overlap with newInterval\n                // merge and update boundary\n                s = min(s, curInterval[START] );\n                e = max(e, curInterval[END] );\n            }\n        }\n        \n        result.insert( result.end(), left.begin(), left.end() );\n        result.push_back( {s, e} );\n        result.insert( result.end(), right.begin(), right.end() );\n        \n        return result;\n        \n        \n    }\nprivate:\n    vector< vector<int> > result;\n};\n```\n\n---\n
['Math', 'C', 'Iterator', 'Python', 'Python3', 'JavaScript']