插入区间

插入区间

http://www.nowcoder.com/questionTerminal/02418bfb82d64bf39cd76a2902db2190

循环遍历原有区间,将待插入区间的右端点、左端点分别与当前区间比较,并更新待插入区间的左右端点,代码如下:

//
// Created by jt on 2020/9/29.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i = 0;
        for (; i < intervals.size(); ++i) {
            // 如果新区间的右边界小于当前区间的左边界,终止循环
            // 如果新区间和当前区间有重叠,更新新区间的左右边界
            // 如果新区间的左边界大于当前区间的右边界,将当前区间放入结果
            if (newInterval.end < intervals[i].start) break;
            else if (newInterval.start <= intervals[i].end) {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            } else res.push_back(intervals[i]);
        }
        // 将更新后的新区间放入结果
        res.push_back(newInterval);
        // 将剩余的区间放入结果
        while(i < intervals.size()) {
            res.push_back(intervals[i]);
            ++i;
        }
        return res;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论

相关推荐

07-14 12:29
门头沟学院 Java
后端岗,实习三周感觉有点想跑路了,担心秋招被拉黑,有没有佬是字节HR知道情况的
从零开始的转码生活:你实习三周都想跑路,将来拿到offer真的愿意在这干十几二十年吗
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务