Interval & Sweepline

56. Merge Intervals

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[][]{};
    List<int[]> list = new ArrayList<>();
    Arrays.sort(intervals, new Comparator<int[]>(){
        public int compare(int[] a, int[] b) {
            // if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        }
    });
    int start = intervals[0][0], end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        int[] in = intervals[i];
        if (in[0] > end) {
            list.add(new int[]{start, end});
            start = in[0];
            end = in[1];
        } else {
            end = Math.max(end, in[1]);
        }
    }
    list.add(new int[]{start, end});
    int[][] res = new int[list.size()][2];
    for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
    return res;
}

57. Insert Interval

public int[][] insert(int[][] intervals, int[] newInterval) {
    int i = 0;
    int n = intervals.length;
    // if ()
    List<int[]> res = new ArrayList<>();
    while (i < n && intervals[i][1] < newInterval[0]) {
        res.add(intervals[i++]);
    }
    int start = newInterval[0];
    int end = newInterval[1];
    while (i < n && end >= intervals[i][0]) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    res.add(new int[]{start, end});
    // i++;
    while (i < n) res.add(intervals[i++]);
    int[][] result = new int[res.size()][2];
    for (int k = 0; k < res.size(); k++) result[k] = res.get(k);
    return result;
}

1094. Car Pooling

Use capacity to keep track of the capacity on the vehicle. The capacity is reduced when adding passengers, and the capacity is increased when release passengers. When capacity < 0, return false.

Sort the trips by start location, and loop over the trips. Use a PriorityQueue and rank by end location to extract the earliest ended trips. Release capacity of those ended trips, and check valid.

    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, new Comparator<>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        PriorityQueue<int[]> pq 
           = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int [] b) {
                return a[2] - b[2];
            }
        });
        for (int[] trip : trips) {
            while (!pq.isEmpty() && pq.peek()[2] <= trip[1]) {
                capacity += pq.poll()[0];
            } 
            capacity -= trip[0];
            if (capacity < 0) return false;
            pq.offer(trip);
        }
        return true;
    }

391. Number of Airplanes in the Sky (lintcode)

Java

    public int countOfAirplanes(List<Interval> airplanes) {
        Collections.sort(airplanes, (Interval o1, Interval o2) -> o1.start - o2.start);
        int count = 0, max = 0;
        PriorityQueue<Interval> pq = new PriorityQueue<>(
                (Interval o1, Interval o2) -> o1.end - o2.end);
        for (Interval in : airplanes) {
            if (!pq.isEmpty() && pq.peek().end <= in.start) {
                pq.poll();
            }
            pq.offer(in);
        }
        return pq.size();
    }

Java (TreeMap)

    public int countOfAirplanes(List<Interval> airplanes) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (Interval interval : airplanes) {
            map.put(interval.start, map.getOrDefault(interval.start, 0) + 1);
            map.put(interval.end, map.getOrDefault(interval.end, 0) - 1);
        }
        int count = 0, max = 0;
        for (int key : map.keySet()) {
            count += map.get(key);
            max = Math.max(max, count);
        }
        return max;
    }

252. Meeting Rooms

Sort and determine it the prev and curt interval has overlap.

    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Arrays.sort(intervals, (int[] in1, int[] in2) -> in1[0] - in2[0]);
        int[] prev = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] curt = intervals[i];
            if (curt[0] < prev[1]) {
                return false;
            }
            prev = curt;
        }
        return true;
    }

253. Meeting Rooms II

Sort the intervals by start time, use Heap(PQ) to sort by end time. Loop over all intervals, detect if the latest ended meeting in heap has overlap between the current meeting.

• if yes, add curt to heap

• otherwise extend the previous meeting in heap.

    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) return a[1] - b[1];
                return a[0] - b[0]; // sort by start
            }
        });
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1]) return a[0] - b[0];
                return a[1] - b[1]; // sort by end
            }
        });
        
        for (int[] curt : intervals) {
            if (pq.isEmpty() || pq.peek()[1] > curt[0]) {
                pq.offer(curt);
            } else {
                int[] prev = pq.poll();
                pq.offer(new int[]{prev[0], curt[1]});
            }
        }
        return pq.size();
    }

TreeMap:

    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] in : intervals) {
            map.put(in[0], map.getOrDefault(in[0], 0) + 1);
            map.put(in[1], map.getOrDefault(in[1], 0) - 1);
        }
        int count = 0, max = 0;
        for (int key : map.keySet()) {
            count += map.get(key);
            max = Math.max(max, count);
        }
        return max;
    }

729. My Calendar I

class MyCalendar {
    TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer lowerKey = map.floorKey(start); 
        Integer hiKey = map.higherKey(start);
        if ((lowerKey != null && map.get(lowerKey) > start) 
            || (hiKey != null && hiKey < end)) {
            return false;
        }
        map.put(start, end);
        return true;
    }
}

731. My Calendar II

Use two lists to store intervals, if there is an existing overlap, then add the overlap portion to the next list. When adding a new interval, check if there is a overlap with the second list.

List<int[]> list;
List<int[]> overlap;
public MyCalendarTwo() {
    list = new ArrayList<>();
    overlap = new ArrayList<>();
}

public boolean book(int start, int end) {
    for (int[] o : overlap) {
        if (o[0] < end && o[1] > start) {
            return false;
        }
    }
    for (int[] o : list) {
        if (o[0] < end && o[1] > start) {
            overlap.add(new int[]{Math.max(o[0], start),
                                 Math.min(o[1], end)});
        }
    } 
    list.add(new int[]{start, end});
    return true;
}

732. My Calendar III

TreeMap sweepline

class MyCalendarThree {
    TreeMap<Integer, Integer> treeMap;
    public MyCalendarThree() {
        treeMap = new TreeMap<>();
    }

    public int book(int start, int end) {
        treeMap.put(start, treeMap.getOrDefault(start, 0) + 1);
        treeMap.put(end, treeMap.getOrDefault(end, 0) - 1);
        int ongoing = 0;
        int k = 0;
        for (int value : treeMap.values()) {
            k = Math.max(ongoing += value, k);
        }
        return k;
    }
}

452. Minimum Number of Arrows to Burst Balloons

435. Non-overlapping Intervals

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
      return 0;
    }
   Arrays.sort(intervals, new Comparator<int[]>() {
       public int compare(int[] a, int[] b) {
           if (a[0] == b[0]) return a[1] - b[1];
           return a[0] - b[0];
       }
   }) ;
    int prev = 0;
    int count = 0;
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[prev][1]) { // overlap
            if (intervals[i][1] < intervals[prev][1]) prev = i;
            count++;
        } else {
            prev = i;   
        }
    }
    return count;
}

1229. Meeting Scheduler

Sort the slots by starting time. Use two pointers and calculate the overlap between two slots, if overlap >= duration, return the result. Move the pointer with earlier starting time.

    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a,b)->a[0]-b[0]); // sort increasing by start time
        Arrays.sort(slots2, (a,b)->a[0]-b[0]); // sort increasing by start time
        int i = 0, j = 0;
        List<Integer> res = new ArrayList<>();
        while (i < slots1.length && j < slots2.length) {
            int overlap = Math.min(slots1[i][1], slots2[j][1]) - Math.max(slots1[i][0], slots2[j][0]);
            if (overlap >= duration) {
                    res.add(Math.max(slots1[i][0], slots2[j][0]));
                    res.add(Math.max(slots1[i][0], slots2[j][0]) + duration);
                    break;
            } 
            if (slots1[i][1] < slots2[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }

759. Employee Free Time

    public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
                List<Interval> result = new ArrayList<>();
        List<Interval> list = new ArrayList<>();
        for (List<Interval> l : schedule) {
            list.addAll(l);
        }
        Collections.sort(list, (o1, o2) -> (o1.start - o2.start));
        List<Interval> res = new ArrayList<>();
        int start = list.get(0).start, end = list.get(0).end;
        for (int i = 1; i < list.size(); i++) {
            Interval curt = list.get(i);
            if (end >= curt.start) {
                end = Math.max(end, curt.end);
            } else {
                res.add(new Interval(end, curt.start));
                start = curt.start;
                end = curt.end;
            }
        }
        return res;
    }

352. Data Stream as Disjoint Intervals

Store all number ranges in a TreeMap and detect if there is an overlap or extension.

/** Initialize your data structure here. */
TreeMap<Integer, Integer> map;
public SummaryRanges() {
    map = new TreeMap<>();
}

public void addNum(int val) {
    if (map.containsKey(val)) return;
    if (map.size() == 0) {
        map.put(val, val);
    } else if (map.lowerKey(val) != null && map.get(map.lowerKey(val)) == val - 1
              && map.higherKey(val) != null && map.higherKey(val) == val + 1) {
        int histart = map.higherKey(val);
        int hiend = map.get(histart);
        map.put(map.lowerKey(val), hiend);
        map.remove(histart);
    } else if (map.lowerKey(val) != null && map.get(map.lowerKey(val)) >= val - 1) {
        map.put(map.lowerKey(val), Math.max(val, map.get(map.lowerKey(val))));
    } else if (map.higherKey(val) != null && map.higherKey(val) == val + 1) {
        int histart = map.higherKey(val);
        int hiend = map.get(histart);
        map.put(val, hiend);
        map.remove(histart);
    } else {
        map.put(val, val);
    }
}

public int[][] getIntervals() {
    int[][] res = new int[map.size()][2];
    int i = 0;
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<Integer, Integer> next = (Map.Entry<Integer, Integer>) it.next();
        res[i++] = new int[]{next.getKey(), next.getValue()};
    }
    return res;
}

715. Range Module

Store all ranges in a TreeMap and detect the ones that overlap, starts with the floorKey then higherKey.

TreeMap<Integer, Integer> map;
public RangeModule() {
    map = new TreeMap<>();
}

public void addRange(int left, int right) {
    Integer floorKey = map.floorKey(left);
    if (floorKey != null) {
        int prevLeft = floorKey, prevRight = map.get(floorKey);
        if (left <= prevRight)  {
            left = Math.min(left, prevLeft);
            right = Math.max(right, prevRight);
        }
    }
    map.put(left, right);
    Integer higherKey = map.higherKey(left);
    while (higherKey != null && higherKey <= right) {
        right = Math.max(map.get(higherKey), right);
        map.remove(higherKey);
        map.put(left, right);
        higherKey = map.higherKey(left);
    }
}

public boolean queryRange(int left, int right) {
    Integer floorKey = map.floorKey(left);
    return floorKey != null && map.get(floorKey) >= right;
}

public void removeRange(int left, int right) {
    addRange(left, right);
    Integer floorKey = map.floorKey(left);
    int left1 = floorKey, right2 = map.get(floorKey);
    int right1 = left, left2 = right;
    map.remove(floorKey);
    if (left1 < right1) { map.put(left1, right1); }
    if (left2 < right2) { map.put(left2, right2); }
}