Merge Intervals

Problem

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

Challenge

O(n log n) time and O(1) extra space.

Note

忘了这题怎么做，汗颜无地。

1. 边界: size < 2

2. sort by Comparator<Interval>

3. loop: merge & removal

4. return

Solution

public class Interval {
    int start, end;
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() < 2) return intervals;
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval l1, Interval l2) {
                return l1.start - l2.start;
            }
        });
        Interval pre = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start <= pre.end) {
                pre.end = Math.max(pre.end, cur.end);
                intervals.remove(cur);
                i--;
            }
            else pre = cur;
        }
        return intervals;
    }
}

Number of Airplanes in the Sky

Problem

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Notice

If landing and flying happens at the same time, we consider landing should happen at first.

Example

For interval list

[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]

Return 3

Note

用HashMap记录每个时刻的飞行数目。
对于某一时刻，起飞和降落同时发生，只计算一次。

Solution

class Solution {
    public int countOfAirplanes(List<Interval> airplanes) { 
        Map<Integer, Integer> map = new HashMap<>();
        int max = Integer.MIN_VALUE;
        if (airplanes == null || airplanes.size() == 0) return 0;
        for (Interval cur: airplanes) {
            for (int i = cur.start; i < cur.end; i++) {
                if (map.containsKey(i)) map.put(i, map.get(i)+1);
                else map.put(i, 1);
                max = Math.max(max, map.get(i));
            }
        }
        return max;
    }
}

Insert Interval

Problem

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

Note

先强势插入，再merge

Solution

class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        
        //check null condition;
        if (intervals == null || intervals.size() == 0) {
            if (newInterval != null) {
                intervals.add(newInterval);
            }
            return intervals;
        }
        
        //add newInterval in right position no matter if it's overlapped;
        int start = newInterval.start;
        int pos = -1;
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals.get(i).start <= start) {
                pos = i;
            }
        }
        intervals.add(pos+1, newInterval);
        
        //merge the intervals;
        Interval pre = intervals.get(0);
        Interval cur = pre;
        for (int i = 1; i < intervals.size(); i++) {
            cur = intervals.get(i);
            if (pre.end >= cur.start) {
                pre.end = pre.end > cur.end ? pre.end: cur.end;
                //.remove(i) followed by i-- to stay in this position after next loop i++
                intervals.remove(i);
                i--;
            }
            else pre = cur;
        }
        
        return intervals;
    }
}