LeetCode 57. Insert Interval 插入区间 (C++/Java)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 57. Insert Interval 插入区间 (C++/Java),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2070字,纯文字阅读大概需要3分钟。
内容图文
![LeetCode 57. Insert Interval 插入区间 (C++/Java)](/upload/InfoBanner/zyjiaocheng/642/5e4dda7b3a414199b1a0eda4d0f74d31.jpg)
题目:
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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Example 2:
Input: intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]]
, newInterval =[4,8]
Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval[4,8]
overlaps with[3,5],[6,7],[8,10]
.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
分析:
给定一个无重叠的,已排序的区间集合,要求在集合中插入一个新的区间,保证插入后区间无重叠且有序。
LeetCode 56. Merge Intervals 合并区间 (C++/Java)的进阶,我们可以利用56题的解法来解决这道题,也就是在原列表中按序将新区间插入,然后再进行区间合并。
此外我们还可以将原集合区间分为三部分,一部分是右端点小于新区间左端点,一部分是左端点大于新区间右端点,这两部分区间不会和新区间发生合并,剩下的区间则需要和新区间合并,遍历完所有区间后,将三部分合并即可。
C++采用插入排序合并,Java采用分区合并
程序:
C++
class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { auto it = intervals.begin(); while(it != intervals.end() && (*it)[0] < newInterval[0]) it++; intervals.insert(it, newInterval); vector<vector<int>> res; for(auto interval:intervals){ if(res.empty()) res.push_back(interval); else if(res.back()[1] < interval[0]) res.push_back(interval); else{ auto t = res.back(); res.pop_back(); res.push_back({t[0], max(t[1], interval[1])}); } } return res; } };
Java
class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int start = newInterval[0]; int end = newInterval[1]; List<int[]> l = new ArrayList<>(); List<int[]> r = new ArrayList<>(); for(int[] interval:intervals){ if(interval[1] < start){ l.add(interval); }else if(end < interval[0]){ r.add(interval); }else{ start = Math.min(start, interval[0]); end = Math.max(end, interval[1]); } } l.add(new int[]{start, end}); l.addAll(r); return l.toArray(new int[l.size()][]); } }
内容总结
以上是互联网集市为您收集整理的LeetCode 57. Insert Interval 插入区间 (C++/Java)全部内容,希望文章能够帮你解决LeetCode 57. Insert Interval 插入区间 (C++/Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。