`
huntfor
  • 浏览: 201544 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Insert Interval

 
阅读更多

这道题。。。。简直了。。。

新博文地址:[leetcode]Insert Interval 

Insert Interval

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].

 这道题不难,就是烦,考虑了各种cover的组合情况,代码繁杂,看着就不对劲,网上搜了一下,找到了这样一个犀利的解法,抽象、简洁、易懂,真经典

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    	List<Interval> list = new LinkedList<Interval>();
    	if(intervals == null || intervals.isEmpty()){
    		list.add(newInterval);
    		return list;
    	}
    	if(newInterval == null) return intervals;
    	int newStart = newInterval.start,newEnd = newInterval.end;
    	int i = 0;
    	for(; i < intervals.size() && intervals.get(i).end < newInterval.start; i++){
    		list.add(intervals.get(i));
    	}
    	if(i < intervals.size()){
    		newStart = Math.min(intervals.get(i).start,newStart);
    	}
    	for(; i < intervals.size() && newEnd >= intervals.get(i).start; i++){
    		newEnd = Math.max(newEnd, intervals.get(i).end);
    	}
    	list.add(new Interval(newStart, newEnd));
    	for(;i < intervals.size(); i++){
    		list.add(intervals.get(i));
    	}
    	return list;
    }

 

分享到:
评论

相关推荐

    java-leetcode题解之Insert Interval.java

    java java_leetcode题解之Insert Interval.java

    js-leetcode题解之57-insert-interval.js

    js js_leetcode题解之57-insert-interval.js

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

    * Insert Interval:该题目要求将一个区间插入到另一个区间中,实现方法使用了排序和迭代算法。 三、字符串和动态规划 * String to Integer (atoi):该题目要求将字符串转换成整数,实现方法使用了状态机算法。 * ...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    Leetcode部分解答(126题)

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

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

    10. Insert Interval 区间插入是一个数组问题,要求将一个区间插入到已经排序的区间数组中。可以使用二分搜索来解决该问题。 11. Two Sum 两数之和是一个经典的数组问题,要求找到数组中两个元素之和等于目标值的...

    _leetcode-python.pdf

    - Insert Interval: 在一组已经排序的区间中,插入一个新的区间。 - Rotate List: 给定一个链表的头节点head,当旋转了k个位置后,返回链表的新头节点。 - Unique Paths / Unique Paths II: 前者计算从矩阵的左上角...

    C语言入门-leetcode练习之第57题插入区间.zip

    在本资源包中,我们关注的是C语言的学习以及如何通过LeetCode平台进行编程练习,特别是针对第57题“插入区间”(Insert Interval)的解题方法。LeetCode是一个在线平台,提供了各种算法题目,旨在帮助程序员提升技能...

    颜色分类leetcode-leetcode.etc:OJ、leetcode等解决方案

    颜色分类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

    leetcode答案-exercise-book:算法练习记录

    Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解。 2018-08-19 19:16 LeetCode: 79. Word Search 解决方法:DFS LeetCode: 31...

    c++-c++编程基础之leetcode题解第57题插入区间.zip

    第57题,"插入区间"(Insert Interval),是其中一道挑战性较高的问题,旨在检验开发者对区间操作、数据结构以及排序算法的理解。下面将详细探讨这个问题的背景、解题策略以及相关的C++编程知识点。 问题描述: ...

    python-leetcode面试题解之第57题插入区间-题解.zip

    def insert(self, intervals, new_interval): intervals.append(new_interval) intervals.sort(key=lambda x: x.start) merged_intervals = [] for interval in intervals: if not merged_intervals or ...

    gasstationleetcode-LeetCode:力码

    leetcode 力码 【吾生也有涯,而知也无涯。】 刷题解题记录: 大批: 220 包含重复 III 考 55 跳跃游戏45 跳跃游戏 II121 买卖股票的最佳时机 122 买卖股票的最佳时机 II123 买卖股票的最佳时机 III188 买卖股票的...

    Coding Interview In Java

    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 ...

Global site tag (gtag.js) - Google Analytics