Intersections of Two Intervals

Given two arrays of sorted non-overlap intervals, try to find all intersections of the intervals.

eg. Interval = [lower bound, upper bound] Array[Interval]

A = [(1,2), (3,4), (7, 10), (15,16)]

B = [(0,2), (3, 8), (8, 12), (16,17)]

A = [(7, 10)], B = [(3, 8), (8, 12)]; 输出[(7, 8), (8, 10)]

详细讨论：http://www.1point3acres.com/bbs/thread-301979-1-1.html

http://www.1point3acres.com/bbs/thread-314872-1-1.html

有一个一直在变的curr 两个list移动指针 目前移动到A 如果curr , A不重叠 把curr 加进list 不然的话 update curr to be the merged interval

Solution 1: Two Pointers O(m + n); O(1)

这题Merge Intervals不同的是：这题是求两个区间数组交集（因为已经排序好，所以很自然想到双指针），Merge Intervals那题是在一个区间数组中合并重叠区间（排序后找重叠合并即可）。

public class IntersectionsOfTwoIntervals {
    public List<Interval> intersection(List<Interval> intervals1, List<Interval> intervals2) { //A, B
        List<Interval> res = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < intervals1.size() && j < intervals2.size()) {
            int start = Math.max(intervals1.get(i).start, intervals2.get(j).start);
            int end = Math.min(intervals1.get(i).end, intervals2.get(j).end);
            if (start < end) {
                res.add(new Interval(start, end));
            }
            if (intervals1.get(i).end < intervals2.get(j).end) {
                i++;
            } else {
                j++;
            }
        }
        for (Interval item : res) {
            System.out.println(item.start + " " + item.end);
        }
        return res;
    }

    public static void main(String[] args) {
        IntersectionsOfTwoIntervals test = new IntersectionsOfTwoIntervals();
        List<Interval> intervals1 = new ArrayList<>();
        intervals1.add(new Interval(1, 2));
        intervals1.add(new Interval(3, 4));
        intervals1.add(new Interval(7, 10));
        intervals1.add(new Interval(15, 16));
        List<Interval> intervals2 = new ArrayList<>();
        intervals2.add(new Interval(0, 2));
        intervals2.add(new Interval(3, 8));
        intervals2.add(new Interval(8, 12));
        intervals2.add(new Interval(16, 17));
        test.intersection(intervals1, intervals2);
    }
}

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

Follow Up:

比如A=[(1,2), (1M, 1M+1)], B=[(1,2) (3,4), ... ... (1M, 1M+1)] 这种case能不能优化一下。

我说的Binary search，找到相近的interval区间。面试官说okay,但是后来想起来binary search还是有很多问题的。