Insert Interval & Merge Intervals-白红宇

Insert Interval & Merge Intervals

阅读量：4364 次

发布时间：2019-06-07

本文共 3189 字，大约阅读时间需要 10 分钟。

Insert Intervals

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

分析：

Create a new array list, insert the smaller interval in the new array and use a counter to keep track of the total number of smaller intervals. If we find an interval overlapping with the new one, we need to change the start and end.

1 /** 2  * Definition for an interval. 3  * public class Interval { 4  *     int start; 5  *     int end; 6  *     Interval() { start = 0; end = 0; } 7  *     Interval(int s, int e) { start = s; end = e; } 8  * } 9  */10 public class Solution {11     public List
       
         insert(List
        
          intervals, Interval newInterval) {12         if (newInterval == null) return intervals;13 14         List
         
           results = new ArrayList<>();15         int insertPos = 0;16 17         for (Interval interval : intervals) {18             if (interval.end < newInterval.start) {19                 results.add(interval);20                 insertPos++;21             } else if (interval.start > newInterval.end) {22                 results.add(interval);23             } else {24                 newInterval.start = Math.min(interval.start, newInterval.start);25                 newInterval.end = Math.max(interval.end, newInterval.end);26             }27         }28         results.add(insertPos, newInterval);29         return results;30     }31 }

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [  [1, 3],               [1, 6],  [2, 6],      =>       [8, 10],  [8, 10],              [15, 18]  [15, 18]            ]] Analyze: Sort first, then merge intervals if they overlap.

1 /** 2  * Definition for an interval. 3  * public class Interval { 4  *     int start; 5  *     int end; 6  *     Interval() { start = 0; end = 0; } 7  *     Interval(int s, int e) { start = s; end = e; } 8  * } 9  */10 public class Solution {11     public List
         
           merge(List
          
            list) {12         if (list == null || list.size() <= 1) return list;13         14         // Collections.sort(list, (Interval a, Interval b) -> a.start - b.start);15         list.sort((i1, i2) -> Integer.compare(i1.start, i2.start));16         17         for (int i = 1; i < list.size(); i++) {18             if (overlap(list.get(i), list.get(i - 1))) { 19                 list.get(i - 1).start = Math.min(list.get(i).start, list.get(i - 1).start);  20                 list.get(i - 1).end = Math.max(list.get(i).end, list.get(i - 1).end); 21                 list.remove(i);22                 i--;23             }24         }  25         return list;26     }27     28     boolean overlap(Interval i1, Interval i2) {  29         return Math.max(i1.start, i2.start) <= Math.min(i1.end, i2.end);  30     }31 }