LeetCode Interval类题目的个人总结（Java描述）

为了方便自己日后面试前的复习，花了两天时间总结了Interval相关的问题，主要包含如下题目：

• 56 Merge Intervals
• 57 Insert Interval
• 252 Meeting Rooms
• 253 Meeting Rooms II
• 352 Data Stream as Disjoint Intervals
• 435 Non-overlapping Intervals
• 436 Find Right Interval
• 616 Add Bold Tag in String
• 636 Exclusive Time of Functions
• 699 Falling Squares
• 715 Range Module
• 759 Employee Free Time
• 986 Interval List Intersections
  

练习的时候除了参考LeetCode讨论版区里的答案以外，还重点参考了两篇文章：

Medium:
https://medium.com/cracking-the- ... amming-a8c019928405
知乎：
https://zhuanlan.zhihu.com/p/26657786

这是我自己第一次系统性地总结刷题的一个分类，希望大家拍砖轻点。
请注意，不能保证总结文档里的思路和方案是100%正确！主要目的是交流，希望读过的朋友帮我指出里面存在的问题，一起讨论一起进步；也希望帮助到有需要的同学。
谢谢！

真好，我还没达到楼主总结的这种水平，于是我决定，今天把上面的题目全做乐。谢谢~

赞 awesome

赞赞赞！！

很有用的信息！

谢谢楼主 非常有用 interval是个大考点

赞一个！紫薯紫薯

452也是同类型的题目，可以补充进去。

xiana406 发表于 2019-5-4 18:23
452也是同类型的题目，可以补充进去。

非常感谢，我加进去的。

xiana406 发表于 2019-5-4 18:23
452也是同类型的题目，可以补充进去。

文档我就暂时不更新了，我会在这个主题下更新，到一定阶段再更发布更新的文档。

452. Minimum Number of Arrows to Burst Balloons
这道题也是Interval的类型，解题思路也是排序和贪心算法。

贪心算法的思路是：尽量找一支箭可以刺穿的气球数，也就是找交集。

以下是我的代码，可能不是最优最简洁的，但是我觉得比较好理解。

1.     public int findMinArrowShots(int[][] points) {
   
2.         Arrays.sort(points, (a, b) -> a[0] - b[0]);
   
3.         if (points.length <= 1) return points.length;
   
4. 
   
5.         int[] intersection = points[0];
   
6.         int count = 1;
   
7.         for (int i = 1; i < points.length; i++) {
   
8.             int[] next = points[i];
   
9. 
   
10.             intersection = intersection(intersection, next);
    
11.             if (intersection == null) {
    
12.                 count++;
    
13.                 intersection = next;
    
14.             }
    
15.         }
    
16. 
    
17.         return count;
    
18.     }
    
19. 
    
20.     private int[] intersection(int[] a, int[] b) {
    
21.         if (a[1] < b[0] || a[0] > b[1]) return null;
    
22. 
    
23.         return new int[]{Math.max(a[0], b[0]), Math.min(a[1], b[1])};
    
24.     }

复制代码

再次谢谢 @xiana406

补充内容 (2019-5-4 19:36):
不好意思，笔记本太老旧了，打字老丢字：贪心算法是让一支箭刺穿尽量多的气球，也就是求交集。