【LC总结】Intervals题目 (Insert/Merge/Number of Airplane

Achilles 发布于2019-08-14 15:50 / 1368人阅读

摘要：忘了这题怎么做，汗颜无地。边界用记录每个时刻的飞行数目。对于某一时刻，起飞和降落同时发生，只计算一次。先强势插入，再

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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