leetcode 区间

本次题解包括

  • 56. Merge Intervals
  • 57. Insert Interval

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

题目地址:leetcode Merge Intervals

题目大意: 给定一些区间,进行合并

思路:按照区间的左端点进行排序,从左到右扫描,判断能否合并即可。水~

C++

Python

 


 

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

题目地址:leetcode Insert Interval

题目大意: 给定已经合并好的区间(并且按照左端点从小到大),插入一个区间进去,必要时进行合并

思路:

和上面一题差不多,只不过不用排序。可以用二分搜索找到要插入的区间位置,插入然后合并即可。

当然不一定要二分,顺序搜索也行,复杂度都是O(n)。

C++

 

Python

 

本文是leetcode如下的题解

  • 56. Merge Intervals
  • 57. Insert Interval

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 区间
本文地址:https://www.hrwhisper.me/leetcode-intervals/

听说长得好看的已经打赏了

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *