Interval Problem:

Sort by end point may be better, why? its kind of greedy solution

swip line solution could solve this kind of problem as well.

Meeting Room II

This solution is kind of swipe line problem, If we sort all intervals' start and end point, we can swipe all intervals efficiently.

The best solution is: O(NlogN)

put all start and end point into two array respectively and sort it. less space
traversal all start points and arrange every meeting
1. every start time means one more meeting and one more room room++
  1. but if current start time is larger than previous end time that means we can use it, so room--
  2. at same time move previous end pointer to next one.

This code is output all of most busy Intervals of Meeting Room.

public int minMeetingRooms(Interval[] intervals) {
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];
    for (int i = 0; i < intervals.length; ++i) {
        starts[i] = intervals[i].start;
        ends[i] = intervals[i].end;
    }
    Arrays.sort(starts);
    Arrays.sort(ends);

    List<Interval> res = new ArrayList<>();
    int e = 0, max = 0, room = 0;
    for (int s = 0; s < starts.length; ++s) {
        room++;
        if (starts[s] >= ends[e]) {
            room--;
            if (room > max) {
                max = room;
                res.clear();
                res.add(new Interval(starts[s - 1], ends[e]));
            } else if (room == max) {
                res.add(new Interval(starts[s - 1], ends[e]));
            }
            e++;
        }

    }
    if (starts.length >= 1) {
        res.add(new Interval(starts[starts.length - 1], ends[e]));
    }
    return room;
}

Merge Intervals

Sort start vs sort both start and end?

Sort all intervals by start time.
compare current start with previous end time
1. current start <= previous end --> No need to merge current interval preEnd = max(preEnd, curEnd)
2. current start > pervious end --> push new Interval into result and update previous start and end

public List<Interval> merge(List<Interval> intervals) {
    if (intervals == null || intervals.size() <= 1) return intervals;
    Collections.sort(intervals, (a,b) -> (a.start - b.start));
    List<Interval> res = new ArrayList<>();

    int preStart = intervals.get(0).start, preEnd = intervals.get(0).end;
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals.get(i).start <= preEnd) {
            preEnd = Math.max(preEnd, intervals.get(i).end);          // should not update it directly
        } else {
            res.add(new Interval(preStart, preEnd));
            preStart = intervals.get(i).start;
            preEnd = intervals.get(i).end;
        }
    }
    res.add(new Interval(preStart, preEnd));
    return res;
}

Insert Interval

这题看似跟前面两题有相似的地方，而且在有序的时候是考虑用Binary Search，但是用这种方法更clean，O(n)

找到需要插入的点，List.add(int pos, object)
只需要更新newInterval

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
      List<Interval> res = new ArrayList<Interval>();
      int pos = 0;
      for (Interval i : intervals) {
            if (i.end < newInterval.start) {
                  ans.add(i);
                  insertPos++;
            } else if (i.start > newInterval.end) {
                  ans.add(i);
            } else {
                  newInterval.start = Math.min(i.start, newInterval.start);
                  newInterval.end = Math.max(i.end, newInterval.end);
            }
      }
      ans.add(insertPos, newInterval);
      return res;
 }

Non-overlapping Intervals

public int eraseOverlapIntervals(Interval[] intervals) {
    Collections.sort(intervals, (a, b) -> a.start - b.start); 
    int end = Integer.MIN_VALUE;
    int count = 0;
    for (Interval interval : intervals) {
        if (interval.start >= end) end = interval.end;
        else count++;
    }
    return count;

Maximum Length of Pair Chain

public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, ((a, b) -> ((a[1] == b[1]) ? (a[0] - b[0]) : (a[1] - b[1]))));
    int res = 0, preEnd = Integer.MIN_VALUE;
    for (int[] pair : pairs) {
        if (pair[0] > preEnd) {
            res++;
            preEnd = pair[1];
        }
    }
    return res;
}

Interval Problem