Interval Questions

how to merge intervals without any intersections?

Analysis :

what is no intersection?

if(prev.end < cur.start (be careful about equal sign)) {

disjoint

} else {

could merge to smallest start and largest end.

}

[1,2], [0,3], [2,5], [6,7] -> [0,5] [6,7]

[0,3] [2,5] ->[0,5] [6,7]

Insert interval

• the whole interval will not be in result

  • left side of interval.start
  • right side of interval.end

[0,2] [3,5] [6,7] + [1,4] -> [0,5] [6,7]

Prerequisite:

sorted by start index.

Way of Thinking I:

prev,next. two by two. one pass

if insert.start < p1.end, insert.end > p2.start

could be merge from [p1,insert,p2]

new_start is min of (p1.start, p2.start, insert.start).

new_end is max of (p1.end, p2.end, insert.end).

prev = cur, cur = next;

Way of Thinking II:

substraction, two pass.

[0,2] [2,5] [6,7] -> merge [0,5] [6,7]

Determine if a target point is covered by a list of intervals(not intersect), sorted by start.

[0,2] [4,6] [7,10] list is sorted by start

is 1 covered ? 3 covered?

Main Idea:

if an interval is at left side of interval, or right side of interval,can't be covered

find interval.start <= target && interval.end >= target

-> must be same interval

public boolean covered (List<Interval> intervals, int target){
    // do sanity check here
    int left = 0, right = interval.size() - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        Interval inter = intervals.get(mid);
        if (inter.start >= target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    Interval li = intervals.get(left), ri = intervals.get(right);
    if(ri.start <= target && ri.end >= target) {
        return true;
    } 
    return li.start <= target && li.end >= target;
}

Determine if a interval is covered \/ intersected with a list of intervals.

interval list is sorted.

1.1 prerequisite: disjoint intervals

Method 1:

-> considering all cases satisfying requirements:

case 1 : covered -> any.start <= cur.start && cur.end <= any.end

case 2: intersected:

          starting point at intervals : any.start <= cur.start <= any.end

          ending point at intervals : any.start <= cur.end <= any.end.

Method 2:

How to divide and conquer?

Considering starting point:

cur.start <= target.start, if cur.end >= target.start, we are done.

cur.start > target.start, if cur.start <= target.end, we are done.

else we can't find one.

1.2 intervals may have overlaps

[0,2] [4,12] [8,10] [12,14]

is 11 covered?

Solution 1: merge list to disjoint intervals, do binary search.

Time: O(n + log n)

Solution 2: if can't merge, must query on original interval list.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

| | | |

Given login interval and current timestamp, track online users amount.

<start_timestamp, end_timestamp>, track all numbers of users logged in.

[0,5] [2,4] [3,7]

0 2 3 4 5 7

1 2 3 2 1 0

Sweep Line algorithm

int count (List<Interval> ls, Interval query) {
   int start = query.start;
   int end = query.end;
   Collections.sort(ls, new Comparator<Interval>({
         @Override
         public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start,i2.start);
         }
   });
   int count = 0;
   for(int i = 0; i < ls.size(); i++) {
      Interval cur = ls.get(i);
      if (cur.start >= start) {
           count++;
      }
      if (cur.end >= end) {
           count--;
      }
   }
   return count;
}

Given a list of flight schedules indicating arrival, departure time, calculate most planes in the sky at any given time?

Solution 1: based on time range.

Way of thinking:

1) identify time range <start, end>

2) at each time, count how many planes, record globalMax.

Time Complexity: O(range * #schedule).

range is large, but schedule is sparse.

Solution 2 : mark time interval boolean value.

[1,4] [2,3]

s e s e

1 2 3 4

s s e e

1 2 1 0

if flight is very tight, 很密集，range又很小，这个算法不太好.

Solution 3 : based on each flight

for each flight, find how many flights any.start >= cur.start && any.end >= cur.end.