**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

**- Sweep line algorithm**

**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

LettCode 452 - Minimum Number of Arrows to Burst Balloons

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

- TreeSet

LeetCode 436 - Find Right Interval

- Use TreeMap to store intervals

- Use TreeMap

- 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.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

```
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 Conquerhttps://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; i
```int

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 Comparatorhttps://discuss.leetcode.com/topic/25503/java-another-thinking-process-event-queue/() { 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; }

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;
}