[LeetCode] Insert Interval 二分搜索
2024-08-28 22:32:26
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
.
This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
Hide Tags
这题是给定一组区间,然后再有一个区间,把重叠的区间合并,合并后的区间输出。
思路1:
简单的想法便是顺序遍历,将新的区间加入后排序,然后合并重叠的,之前写过了这个。
思路2:
思路1 合并的只会操作一次,所以换一个,因为一组区间是有序的,所以可以试图找出合并的头、尾,这样便能够加速。为了快速定位合并的头尾,可以使用二分搜索。
我定义了一个二分搜索,用于查找一组区间中,按头比较,找出不大于target 的最大区间头的idx。
这样便有了大概的定位,然后把一组区间中做部分的加入返回,然后创造新的区间,加入返回,最后把剩余的后部区间加入返回。
需要注意的是创造区间有可能并不与其他合并,即 加入的区间 不和其他区间重叠,比较麻烦的是确定切割的地方。
#include <vector>
#include <iostream>
using namespace std;
/**
* Definition for an interval.
*/
struct Interval {
int start;
int end;
Interval() : start(), end() {}
Interval(int s, int e) : start(s), end(e) {}
}; class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
int n = intervals.size();
if(n<) return vector<Interval>{{newInterval.start,newInterval.end}};
vector<Interval> ret;
// if(n==1){
// if(newInterval.end<intervals[0].start){
// ret.push_back(newInterval); ret.push_back(intervals[0]);
// return ret;
// }
// if(intervals[0].end<newInterval.start){
// ret.push_back(intervals[0]); ret.push_back(newInterval);
// return ret;
// }
// }
int idx1 =binsearch(intervals,newInterval.start);
int idx2 =binsearch(intervals,newInterval.end);
int idx_tmp,newStart;
if(intervals[idx1].end>=newInterval.start){
idx_tmp = idx1-;
newStart = intervals[idx1].start<newInterval.start?intervals[idx1].start:newInterval.start;
}
else{
idx_tmp=idx1;
newStart = newInterval.start;
}
for(int i=;i<=idx_tmp;i++) ret.push_back(intervals[i]);
int newEnd;
if(newInterval.end<intervals[idx2].start){
newEnd = newInterval.end;
idx_tmp = idx2;
}
else{
newEnd = intervals[idx2].end>newInterval.end?intervals[idx2].end:newInterval.end;
idx_tmp = idx2+;
}
ret.push_back(Interval(newStart,newEnd));
for(int i=idx_tmp;i<n;i++) ret.push_back(intervals[i]);
return ret;
} int binsearch(vector<Interval> &ints,int target)
{
if(ints.size()==) return ;
int lft = ,rgt = ints.size()-;
if(ints[rgt].start<=target) return rgt;
if(ints[lft].start>=target) return lft;
int ret = ;
do{
int mid = (lft+rgt)/;
if(ints[mid].start>target) rgt=mid;
else lft=mid;
ret = lft;
if(ints[ret+].start>target) break;
}while(lft+<rgt);
return ret;
}
}; int main(){
vector<Interval> intervals{{,},{,},{,},{,},{,}};
// vector<Interval> intervals{{1,2}};
// cout<<intervals[0].start<<" "<<intervals[1].end<<endl;
Interval newInterval(-,);
Solution sol;
vector<Interval> ret = sol.insert(intervals,newInterval);
for(int i=;i<ret.size();i++)
cout<<ret[i].start<<" "<<ret[i].end<<endl;
return ;
}
最新文章
- java 中正则表达式匹配
- dubbo源码分析2-reference bean发起服务方法调用
- 网页JS获取当前地理位置(省市区)
- SVN标准命令
- ARC指南2 - ARC的开启和禁止
- TCP/IP详解学习笔记(12)-- TCP:传输控制协议
- ORACLE DATAGURARD 折腾记二
- softmax
- jrae源码解析(一)
- BZOJ1511: [POI2006]OKR-Periods of Words
- 面试之get和post(转)
- K. Perpetuum Mobile
- Navicat 连接远程服务器mysql 长时间不操作会连接很久
- (后端)mybatis中使用Java8的日期LocalDate、LocalDateTime
- MonkeyRunner测试工具小结
- BZOJ1004 HNOI2008 Cards Burnside、背包
- vuex的module的简单实用方法
- bzoj4504 K个串 (优先队列+主席树)
- UI5-文档-4.6-Modules
- zz 启动Matlab提示Microsoft Visual C++ 2005 Redistributable存在问题问题