题解 | #合并区间#

合并区间

http://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:

    static bool cmp (const Interval a, const Interval b) { // 先按照start从小到大排序,然后按照end从大到小排序
        return a.start < b.start || (a.start == b.start) && a.end > b.end;
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> res;
        int n = intervals.size();
        if(n < 1) // 将n<1和n<2先讨论
            return res;
        if(n < 2) {
            res.push_back(intervals[0]);
            return res;
        }
        sort(intervals.begin(), intervals.end(), cmp); // 将intervals数组排序
        auto pre = intervals[0]; // 设置pre保留遍历前一个元素
        for(int i = 1; i < n; i++) {
            auto cur = intervals[i];
            if(cur.end <= pre.end) // 分三种情况讨论
                continue;
            else if(cur.start <= pre.end)
                pre.end = cur.end;
            else{
                res.push_back(pre); // 当前一个元素与当前元素没有交集时,将前一个元素压入数组,并将pre更新为当前元素
                pre = cur;
            }
        }
        res.push_back(pre); // 将最后的元素压入数组
        return res;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
2022-12-10 18:47
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议