【LeetCode-面试算法经典-Java实现】【057-Insert Interval(插入区间)】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode-面试算法经典-Java实现】【057-Insert Interval(插入区间)】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1903字,纯文字阅读大概需要3分钟。
内容图文
【057-Insert Interval(插入区间)】
【LeetCode-面试算法经典-Java实现】【所有题目目录索引】
原题
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]
.
题目大意
给定一系列非覆盖的区间,插入一个新的区间,有必要的时候进行区间合并,区间开始是以起始时间进行合并的
解题思路
如果原来的区间比插入区间小就插入结果集,如果插入区间有重叠,更新插入区间,如果插入区间小于原来的区间,先插入插入区间,再添加大的区间
代码实现
算法实现类
import java.util.LinkedList;
import java.util.List;
publicclassSolution {public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
// 保存结果的集合
List<Interval> result = new LinkedList<>();
// 输入集非空if (intervals != null) {
// 遍历元素for (Interval item : intervals) {
// newInterval == null 表示插入的区间已经处理完了// 将比插入区间小的区间加入结果集中if (newInterval == null || item.end < newInterval.start) {
result.add(item);
}
// 将比插入区间大的区间加入结果集中,同时将插入的区间加入结果集elseif (item.start > newInterval.end) {
result.add(newInterval);
result.add(item);
newInterval = null;
}
// 插入区间有重叠,更新插入区间else {
newInterval.start = Math.min(newInterval.start, item.start);
newInterval.end = Math.max(newInterval.end, item.end);
}
}
}
// 如果插入区间非空说明插入区间还未被处理if (newInterval != null) {
result.add(newInterval);
}
return result;
}
}
评测结果
点击图片,鼠标不释放,拖动一段位置,释放后在新的窗口中查看完整图片。
特别说明
欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47164431】
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/derrantcm/article/details/47164431
内容总结
以上是互联网集市为您收集整理的【LeetCode-面试算法经典-Java实现】【057-Insert Interval(插入区间)】全部内容,希望文章能够帮你解决【LeetCode-面试算法经典-Java实现】【057-Insert Interval(插入区间)】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。