57 | Insert Interval |
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ bool overlap(const Interval &left,const Interval &right){ return !(left.end<right.start||right.end<left.start); } struct Overlap:public std::binary_function<Interval,Interval,bool>{ bool operator()(const Interval &left,const Interval&right)const{ return !(left.end<right.start||right.end<left.start); } }; struct IntervalCompare:public std::binary_function<Interval,Interval,bool>{ bool operator()(const Interval &left,const Interval&right)const{ return left.start<right.start; } }; class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> ans; ans.reserve(intervals.size()); if(intervals.empty()){ ans.push_back(newInterval); return ans; } // std::sort(intervals.begin,intervals.end(),IntervalCompare()); int i=0; Interval merge = intervals[0]; vector<Interval> &merges=intervals; merge = newInterval; if(newInterval.end<merges[0].start) { } else { for(i=0;i<merges.size();i++) { if(Overlap()(merge,merges[i])) { merge.start = std::min(merge.start,merges[i].start); merge.end = std::max(merge.end,merges[i].end); } else { if(merge.end<merges[i].start){ break; } ans.push_back(merges[i]); } } } ans.push_back(merge); ans.insert(ans.end(),merges.begin()+i,merges.end()); return ans; } };
这个其实,像扫描线(sweep)算法(在二维计算几何中,经常用到)
基本思路:注意到已经按照每个Interval的start排序了
<1>将需要检查的newInterval,依次和每个interval合并(循环)
<2>如果发现没有重叠,跳出
<3>添加合并后的merge 区间,添加哪些不与newInterval重叠的区间。
上述,很容易理解,但有个问题:
为什么保证结果一定有序?即按照区间的start排序?
其实,这是因为,<1>中基本上属于插入排序过程,所以结果一定有序。
相关推荐
Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解。 2018-08-19 19:16 LeetCode: 79. Word Search 解决方法:DFS ...
LifeInterval57Insert Interval56Merge Intervals252Meeting Rooms253Meeting客房II352Data流从数据Stream53Maximum Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数...
颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 ...Insert Interval Easy Two Strings Are Anagrams(比较字符串) E
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 (atoi) 59 20 Merge ...
delphi6 使用praat进行音频标注时候,可以把textgrid文件转换成早期的interval文件爱女
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
an Interval Type-2 fuzzy set composed from α-cuts done over its primary membership functions. The defi nition of available Type-reduction methods for Interval Type-2 fuzzy sets are based on an ...
【LeetCode】436. Find Right Interval 解题报告(Python)标签(空格分隔): LeetCode作者: 负雪明烛个人博客: h
1.5.13 Insert方法——插入项 110 1.5.14 Item属性——获取或设置指定索引处的元素 111 1.5.15 Length属性——获取长度 112 1.5.16 Next方法——返回一个指定范围内的随机数 113 1.5.17 Queue类——队列 115 1.5.18 ...
Interval Finite Element Method with MATLAB provides a thorough introduction to an effective way of investigating problems involving uncertainty using computational modeling. The well-known and ...
Interval 、 Employee 列表节点 构造函数 const node = new ListNode ( val ) 使用数组初始化 (遵循 LeetCode 主题规范): ListNode.create(arr : Array) : ListNode const head = ListNode . create ( [ 1 , 2 , ...
资源分类:Python库 所属语言:Python 资源全名:interval-py-0.0.2.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
今天小编就为大家分享一篇Python 数值区间处理_对interval 库的快速入门详解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
题目: Range 模块是跟踪数字范围的模块。你的任务是以一种有效的方式设计和实现以下接口。 addRange(int left, int right) 添加半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的...
' 2、设置 Interval 属性。 ' 3、设置 Enabled 属性,开启或关闭计时器。 ' 4、在 Timer() 事件中添加执行代码。 ' 作 者:鹤望兰·流 ' 发布日期:2010-05-27 ' 网 站:http://hewanglan.ys168.com ' E - mail:...
前端开源库-node-interval-tree节点间隔树,实现间隔树的数据结构。
human-interval, javascript的人类可以读时间 人类间隔Javascript的人类可读区间解析器。由 matthewmueller/日期激发。示例用法const humanInterval = require('human-interval');setTimeout
matlab开发-Intervaltype2fuzzylogic系统的功能。实现区间2型模糊逻辑系统和一种非常有效的类型约简算法。
INSERT INTO warranty VALUES 123 INTERVAL "8" MONTH ; INSERT INTO warranty VALUES 155 INTERVAL "200" YEAR 3 ; INSERT INTO warranty VALUES 678 "200 11" ; SELECT FROM ...
using matlab to solve Confidence Interval