`

56 Merge Intervals——leetcode

阅读更多

这个是基于排序库实现的

56 Merge Intervals
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 struct Overlap{
    bool operator()(const Interval &left,const Interval&right)const{
        return !(left.end<right.start||right.end<left.start);
    }
};
bool overlap(const Interval &left,const Interval &right){
    return !(left.end<right.start||right.end<left.start);
}

struct IntervalCompare{
    bool operator()(const Interval &left,const Interval&right)const{
        return left.start<right.start;
    }
};

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.empty()){
            return intervals;
        }
        std::sort(intervals.begin(),intervals.end(),IntervalCompare());
        int i=0;
        Interval *merge = &intervals[0];
        vector<Interval> merges;
        int merged_i=0;
        for(i=1;i<intervals.size();i++)
        {
            if(Overlap()(*merge,intervals[i]))
            {
                merge->end = std::max(merge->end,intervals[i].end);
            }
            else
            {
                if(merged_i!=i)
                {
                    intervals[merged_i] = *merge;
                }
                ++merged_i;
                
                merge = &intervals[i];
            }
        }
        if(merged_i!=i)
        {
           intervals[merged_i] = *merge; 
        }
        ++merged_i;
        intervals.resize(merged_i);
        return intervals;
    }
};

 同样是合并,没有太大的区别。这里使用了排序库函数,核心在排序。

分享到:
评论

相关推荐

    leetcode56-Leetcode56---Merge-Intervals:Leetcode56---合并间隔

    【标题】"LeetCode56 - 合并间隔"是一个编程挑战,主要涉及算法和数据结构的知识点。在这个问题中,任务是合并一系列非重叠的整数区间,以形成尽可能少的连续区间。 【描述】LeetCode是全球知名的在线编程训练平台...

    java-leetcode题解之Merge Intervals.java

    java java_leetcode题解之Merge Intervals.java

    js-leetcode题解之56-merge-intervals.js

    js js_leetcode题解之56-merge-intervals.js

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode ...LeetCode ...56 Merge Intervals 64 Minimum Path Sum 73

    LeetCodeTrain:这是来自LeetCode的已解决任务的存储库

    这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 CoinChange.java - //leetcode....intervals/ ReverseLinkedList.java - //leetcode.com/problem

    lrucacheleetcode-LeetCodeSheet:记录自己Leetcode之旅

    Intervals 进阶题目: Leetcode 179. Largest Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick ...

    c++-c++编程基础之leetcode题解第56题合并区间.zip

    第56题,"Merge Intervals"(合并区间),是一道典型的区间处理问题,它考察了对排序、遍历以及区间合并的理解。在此,我们将深入探讨这个问题的解决方案,并结合C++编程技巧进行解析。 首先,我们要明确问题描述:...

    leetcode2sumc-LeetCode:练习商务面试

    leetcode 2 sum c LeetCode规划 LEETCODE PATTERNS 从LeetCode学演算法 Leetcode笔记 Leetcode 经典题目 程式题 1) reverse string Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] 使用内部swap class...

    gasstationleetcode-LeetCode:力码

    Interval56Merge Intervals252Meeting Rooms253Meeting客房II352Data流从数据Stream53Maximum Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数的距离和很少考289Game...

    Coding Interview In Java

    11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design 51 16 3Sum 53 17 4Sum 55 18 3Sum Closest 57 19 String to Integer ...

    LeetCode 刷题笔记 with Java.zip

    例如,“Merge Intervals”(合并区间)要求我们合并时间重叠的事件区间,这需要用到排序和区间合并的技巧。"Valid Palindrome"(有效的回文串)则需要理解双指针法和忽略特定字符的策略。 最后的暗黑版《LeetCode ...

    LeetCode题解(java语言实现).pdf

    * Merge Intervals:该题目要求合并重叠的区间,实现方法使用了排序和迭代算法。 * Insert Interval:该题目要求将一个区间插入到另一个区间中,实现方法使用了排序和迭代算法。 三、字符串和动态规划 * String to...

    Codes

    比如,"Merge Intervals"问题,需要将时间区间进行合并,这就需要用到排序和区间处理的算法。 3. 递归与回溯:LeetCode中的很多问题,如"Word Search"或"N-Queens",可以通过递归和回溯法来解决。递归是解决问题的...

    python-leetcode面试题解之第56题合并区间-题解.zip

    在本压缩包中,我们关注的是Python编程与LeetCode在线平台上的面试题解,特别是第56题——“合并区间”。这道题目是面试中常见的数据结构与算法问题,对于求职面试,尤其是针对IT岗位,掌握这样的问题解答能力至关...

    Leetcode部分解答(126题)

    5. **Merge Intervals(using (Insert Interval) ).cpp** - 这是第56题“合并区间”的解冑,涉及到区间操作,尤其是如何有效地插入新区间并合并重叠区间。 6. **Integer to Roman.cpp** - 第40题,与“Roman to ...

    python入门-leetcode面试题解之第228题汇总区间.zip

    本文将深入探讨如何利用Python解决LeetCode上的第228题——汇总区间。我们将从Python基础知识出发,逐步解析问题,展示解题思路,并给出具体代码实现。 首先,让我们理解一下第228题的描述。这道题要求我们给定一个...

    C语言入门-leetcode练习之第56题合并区间.zip

    题目56——合并区间,要求编写一个函数`merge(int* intervals, int intervalsSize, int* returnSize)`,输入是一个二维整数数组`intervals`,表示一系列非空的不重叠时间区间,每个区间由两个整数`[start, end)`表示...

    LeetCode题解 - Java语言实现-181页.pdf

    9. Merge Intervals 区间合并是一个数组问题,要求合并重叠的区间。可以使用排序和迭代来解决该问题。 10. Insert Interval 区间插入是一个数组问题,要求将一个区间插入到已经排序的区间数组中。可以使用二分...

    leetcode482-coding-test:编码测试

    MergeIntervals_56 [Java] Java LinkedList 用法和示例总结 MeetingRoomsII_253 [Java] PriorityQueue 类用法和示例总结 关于 KClosetPointsToOrigin_973 PriorityQueue(报告正确答案) FindAllAnagramsInAString_...

    LeetCode刷题笔记——56. 合并区间

    def merge(self, intervals: List[List[int]]) -&gt; List[List[int]]: intervals = sorted(intervals) # 区间从小到大排序,若左边界相等,则对右边界排序; i = 1 # 初始位置从第二个区间开始 while i = ...

Global site tag (gtag.js) - Google Analytics