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

Achilles 發布于2019-08-14 15:50 / 1376人閱讀

摘要：忘了這題怎么做，汗顏無地。邊界用記錄每個時刻的飛行數目。對于某一時刻，起飛和降落同時發生，只計算一次。先強勢插入，再

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記錄每個時刻的飛行數目。
對于某一時刻，起飛和降落同時發生，只計算一次。

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

先強勢插入，再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;
    }
}

云服務器 GPU云服務器 Intervals LC lc域名 OFS

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66052.html

leetcode56 Merge Intervals

摘要：題目要求輸入一系列區間，將出現交叉的區間合并起來，并將合并后的區間返回。將這兩個數組分別排序可以得到和。也就是說，合并后的結果和是等價的。舉個栗子，輸入為，先判斷是否是獨立區間，可見可以和合并，則將修改為。題目要求 Given a collection of intervals, merge all overlapping intervals. For example, Given...

shmily 2019-08-16 10:37 評論0 收藏0
352. Data Stream as Disjoint Intervals

摘要：題目解答這題用會通過很快定位到當前數所處在哪兩個之間，從而進行高效的比較與合并。題目：Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals. For exampl...

maybe_009 2019-08-14 14:25 評論0 收藏0
leetcode436. Find Right Interval

摘要：題目要求假設一個二維的整數數組中每一行表示一個區間，每一行的第一個值表示區間的左邊界，第二個值表示區間的右邊界。題目要求 Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal ...

robin 2019-08-16 18:34 評論0 收藏0
【LC總結】Iterator題目<Zigzag 1&2><BST>&

摘要：方法直接查找數組的位的迭代器，調用方法得到的整數即為要返回的元素。再寫迭代器的方法返回指針元素的并讓指針通過遞歸方法指向下一個元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

WelliJhon 2019-08-14 15:49 評論0 收藏0
leetcode57. Insert Interval

摘要：題目要求給定一組順序排列且相互之間沒有重疊的區間，輸入一個區間，將它插入到當前的區間數組中，并且將需要合并的區間合并，之后返回插入并且合并后的區間。我們將這三個類型的區間分別標注為類型，類型，類型。題目要求 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge...

Yuanf 2019-08-16 10:37 評論0 收藏0