【LC總結(jié)】Intervals題目 (Insert/Merge/Number of Airplane

Achilles 發(fā)布于2019-08-14 15:50 / 1369人閱讀

摘要：忘了這題怎么做，汗顏無地。邊界用記錄每個(gè)時(shí)刻的飛行數(shù)目。對(duì)于某一時(shí)刻，起飛和降落同時(shí)發(fā)生，只計(jì)算一次。先強(qiáng)勢(shì)插入，再

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

忘了這題怎么做，汗顏無地。

邊界: size < 2

sort by Comparator

loop: merge & removal

return

Solution

public class Interval {
    int start, end;
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
class Solution {
    public List merge(List intervals) {
        if (intervals.size() < 2) return intervals;
        Collections.sort(intervals, new Comparator() {
            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記錄每個(gè)時(shí)刻的飛行數(shù)目。
對(duì)于某一時(shí)刻，起飛和降落同時(shí)發(fā)生，只計(jì)算一次。

Solution

class Solution {
    public int countOfAirplanes(List airplanes) { 
        Map 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

先強(qiáng)勢(shì)插入，再merge

Solution

class Solution {
    public ArrayList insert(ArrayList 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;
    }
}