Interval - Algorithm

When to use interval
- Sort by start or end first
- Kind of Greedy
- sort interval, then binary search (LeetCode 436 - Find Right Interval)
  -- Sort Interval
  -- Or sort start, end separately
  -- Or sort start, end at one array
- Use TreeMap or TreeMap> to store intervals and compare based on start
- Use Priorityqueue
- Sweep line algorithm

- Interval operation: insert, merge interval

X. Interval Binary Search Tree
- How to remove an interval
private class Node {
 Interval interval; // or directly store start, end; start is used as the key to build BST
 Node left, right;
 int maxValue; // the max value of all intervals rooted in this node
}

Unlimited switches
isToggled(long idx)
toggle(long start, long end)

Sort by start
Given n appointments, find all conflicting appointments

LeetCode 616 - Add Bold Tag in String

LettCode 452 - Minimum Number of Arrows to Burst Balloons

LeetCode 435 - Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

LeetCode 436 - Find Right Interval
Sort by start then binary search

Google – Remove Alarm
Google – Find a Path Among Circles
- Only merge interval when two circles intersects

LeetCode 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.
- TreeMap intervals to merge interval based on start
- TreeSet

LeetCode 436 - Find Right Interval
- Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
- Sort Intervals based on start + binary search

LeetCode 253 - Meeting Rooms II
find the minimum number of conference rooms required.
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
Arrays.sort(starts);
Arrays.sort(ends);
- Use PriorityQueue
Arrays.sort(intervals, (a, b) -> { return a.start - b.start;}});
PriorityQueue ends = new PriorityQueue();
ends.offer(intervals[0].end);
https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/2
pq.offer(new Event(interval.start, 1));
pq.offer(new Event(interval.end, 0));

LeetCode 252 - Meeting Rooms
determine if a person could attend all meetings.

LeetCode 56 - Merge Intervals
LeetCode 57 - Insert Interval

LeetCode 218 - The Skyline Problem
Using TreeMap
https://discuss.leetcode.com/topic/22482/short-java-solution
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/28482/once-for-all-explanation-with-clean-java-code-o-n-2-time-o-n-space
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline

Sweepline is used in solving the problem. List height is used to save each of the line segments including both start and end point. The trick here is to set the start segment as negative height. This has a few good uses:

first, make sure the start segment comes before the end one after sorting.

second, when pushing into the queue, it is very each to distinguish either to add or remove a segment.

    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] b: buildings) {
            heights.add(new int[]{b[0], - b[2]});
            heights.add(new int[]{b[1], b[2]});
        }
        Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
        TreeMap heightMap = new TreeMap<>(Collections.reverseOrder());
        heightMap.put(0,1);
        int prevHeight = 0;
        List<int[]> skyLine = new LinkedList<>();
        for (int[] h: heights) {
            if (h[1] < 0) {
                Integer cnt = heightMap.get(-h[1]);
                cnt = ( cnt == null ) ? 1 : cnt + 1;
                heightMap.put(-h[1], cnt);
            } else {
                Integer cnt = heightMap.get(h[1]);
                if (cnt == 1) {
                    heightMap.remove(h[1]);
                } else {
                    heightMap.put(h[1], cnt - 1);
                }
            }
            int currHeight = heightMap.firstKey();
            if (prevHeight != currHeight) {
                skyLine.add(new int[]{h[0], currHeight});
                prevHeight = currHeight;
            }
        }
        return skyLine;
    }

X. Divide and Conquer
https://discuss.leetcode.com/topic/16511/share-my-divide-and-conquer-java-solution-464-ms
http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

 public List<int[]> getSkyline(int[][] buildings) {
  if (buildings.length == 0)
   return new LinkedList<int[]>();
  return recurSkyline(buildings, 0, buildings.length - 1);
 }

 private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
  if (p < q) {
   int mid = p + (q - p) / 2;
   return merge(recurSkyline(buildings, p, mid),
     recurSkyline(buildings, mid + 1, q));
  } else {
   LinkedList<int[]> rs = new LinkedList<int[]>();
   rs.add(new int[] { buildings[p][0], buildings[p][2] });
   rs.add(new int[] { buildings[p][1], 0 });
   return rs;
  }
 }

 private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
  LinkedList<int[]> rs = new LinkedList<int[]>();
  int h1 = 0, h2 = 0;
  while (l1.size() > 0 && l2.size() > 0) {
   int x = 0, h = 0;
   if (l1.getFirst()[0] < l2.getFirst()[0]) {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h = Math.max(h1, h2);
    l1.removeFirst();
   } else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    x = l2.getFirst()[0];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l2.removeFirst();
   } else {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
    l1.removeFirst();
    l2.removeFirst();
   }
   if (rs.size() == 0 || h != rs.getLast()[1]) {
    rs.add(new int[] { x, h });
   }
  }
  rs.addAll(l1);
  rs.addAll(l2);
  return rs;
 }

X. Thought as different kinds of evet: start/end event
LeetCode 253 - Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda

    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; iint

rooms = 0; int endsItr = 0; for(int i=0; iif(starts[i]else endsItr++; } return rooms; }X. Using prority queue + sweep line
http://www.cnblogs.com/yrbbest/p/5012534.html
https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/10

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
        
        Arrays.sort(intervals, new Comparator() {
            public int compare(Interval t1, Interval t2) {
                if(t1.start != t2.start)
                    return t1.start - t2.start;
                else
                    return t1.end - t2.end;
            }
        });
        
        int maxOverlappingMeetings = 0;
        PriorityQueue pq = new PriorityQueue<>();      // min oriented priority queue
        
        for(int i = 0; i < intervals.length; i++) {         // sweeping-line algorithms
            pq.add(intervals[i].end);
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
                pq.remove();
                
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        }
        
        return maxOverlappingMeetings;
    }

https://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/


LeetCode 252 - Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
https://discuss.leetcode.com/topic/31306/easy-java-solution-beat-98
https://discuss.leetcode.com/topic/20959/ac-clean-java-solution

public boolean canAttendMeetings(Interval[] intervals) {
  if (intervals == null)
    return false;

  // Sort the intervals by start time
  Arrays.sort(intervals, new Comparator() {
    public int compare(Interval a, Interval b) { return a.start - b.start; }
  });
  
  for (int i = 1; i < intervals.length; i++)
    if (intervals[i].start < intervals[i - 1].end)
      return false;
  
  return true;
}