Google – Remove Alarm

Google – Remove Alarm
有一堆Alarm, 每个alarm有三个值，start time, end time和priority。要求是把那些从没有成为过最高优先级的alarm给删除。
比如有这么几个alarms:
Alarm1 (1, 2, 1)
Alarm2 (1, 4, 2)
Alarm3 (3, 5, 3)
Alarm4 (3, 4, 2)
那么比如alarm1和alarm4就是要删除的。因为alarm1和alarm2同时开始，但是第二个优先级高，等第二个结束的时候第一个alarm早就结束了。所以第一个alarm从来没有到过最高优先级。alarm4也是一样。
[Solution]
这道题学会了一种新的算法：scan-line algorithm，中文叫扫描线算法。Leetcode里的the skyline problem使用的也是这种算法。
http://www.jiuzhang.com/qa/339/
思路就是把每个alarm的range拆成两条线，每条线记录一下信息：

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

class Line {     int time;     boolean isStart;     int priority;     int id;     Line(int time, boolean isStart, int priority, int id) {       this.time = time;       this.isStart = isStart;       this.priority = priority;       this.id = id;     }   }

1. 对所有Line按照time进行排序，如果time一样的，priority高的在前，如果priority也一样的，start在前，end在后。
2. 遍历所有lines，边遍历边维护一个hash map和一个max heap.
   • hash map用来map priority to set of alarm id
   • max heap用来找最高的priority。
   1. 如果当前line是start, 那么把alarm id加入hash table对应priority的set里，并把priority加入max heap
   2. 如果当前line是end, 那么把alarm id从对应priority的set里删除，如果删除它之后对应的set为空了，那么把这个priority分别从hash table和max heap里删除。
   3. 每处理完一条line，都要从maxHeap里取出最大的priority，再到hash table里把该最大priority的alarm id全部mark一遍，表示这些alarm成为最高priority，不用删除。
3. 最后删除那些没有被mark过的alarm

[Note]
因为这道题涉及到从maxHeap里删除元素，heap的结构是不支持search和delete功能的，所以本质上priority queue的remove方法就是对底层的internal array扫一遍来找到要删除的元素。时间是O(n)，如果不对这个细节做特殊处理的话，整个算法的复杂度会变为O(n²)。
上面的连接里提到了一种Hash Heap的数据结构，就是用一个hash table来映射heap里每个元素的对应位置，这样在remove的时候就可以做到O(1)时间。

---

非常复杂的一道题，算法，思路和数据结构都很新颖。

class Alarm {   int start;   int end;   int priority;   Alarm(int start, int end, int priority) {     this.start = start;     this.end = end;     this.priority = priority;   } } class Solution {   public void removeAlarm(List<Alarm> alarms) {     if (alarms == null || alarms.isEmpty()) {       return;     }     List<Line> Lines = new ArrayList<>();     for (int i = 0; i < alarms.size(); i++) {       Alarm alarm = alarms.get(i);       Lines.add(new Line(alarm.start, true, alarm.priority, i));       Lines.add(new Line(alarm.end, false, alarm.priority, i));     }     Collections.sort(Lines, new Comparator<Line>() {       public int compare(Line a, Line b) {         if (a.time == b.time && a.priority == b.priority) {           return a.isStart? -1 : 1;         }         else if (a.time == b.time) {           return -(a.priority - b.priority);         }         return a.time - b.time;       }     });     Map<Integer, Set<Integer>> priorityMap = new HashMap<>();     PriorityQueue<Integer> maxHeap = new PriorityQueue<>(5, Collections.reverseOrder());     Set<Integer> mark = new HashSet<>();     for (Line Line : Lines) {       if (Line.isStart) {         if (!priorityMap.containsKey(Line.priority)) {           priorityMap.put(Line.priority, new HashSet<>());           maxHeap.offer(Line.priority);         }         priorityMap.get(Line.priority).add(Line.id);       }       else {         priorityMap.get(Line.priority).remove(Line.id);         if (priorityMap.get(Line.priority).isEmpty()) {           priorityMap.remove(Line.priority);           maxHeap.remove(Line.priority);         }       }       if (!maxHeap.isEmpty()) {         int top = maxHeap.peek();         for (int id : priorityMap.get(top)) {           mark.add(id);         }       }     }     for (int i = 0; i < alarms.size(); i++) {       if (!mark.contains(i)) {         System.out.println(i);       }     }   }   private class Line {     int time;     boolean isStart;     int priority;     int id;     Line(int time, boolean isStart, int priority, int id) {       this.time = time;       this.isStart = isStart;       this.priority = priority;       this.id = id;     }   } }

http://www.jiuzhang.com/qa/339/

有一个需要clarify的地方是，如果和其他的alert一起同时成为最高的优先度，这种需要去掉么？

下面的解答基于不需要去掉与其他alarm同时成为最高优先度的那些alarms：

1. 将起始时间终止，终止时间和对应的优先度以及alarm的id打散。一个alarm会变成两个item：(start_time, alarm_id, priority, is_start=true), (end_time, alarm_id, priority, is_start=false)
2. 把所有的2N个items排序。按照第一个field time从小到大排序。
3. 依次访问排序后的每个item
   1. 如果is_start=true，那么 check priority 是否在某个集合中，如果不在的话就create一个entry 给这个priority，将alarm_id添加到该priority的一个list里，表示当前是该priority的alarms有哪些。entry包括两个部分，一个是priority，作为key，第二个是一个list，表示有哪些alarms，作为value。
   2. 如果is_start=false，那么 找到集合中priority对应的entry，然后把alarm_id从里面删除，如果entry里的list空了，就在集合中删除这条entry。
   3. 上面的操作完成后，检查目前集合中priority最高的entry，把这个entry里的alarms都标记为成为过最高优先级的。
4. 最后再check所有的alarm，看看哪些没有被标记过。

这中间有一个优化需要做的是，需要把list分为已经标记过成为最高优先级的，和没有标记过成为最高优先级的。否则反复标记同一个alarm成为过最高优先级会耗费时间复杂度。 这个list，本身因为需要支持插入和删除的话，那么其实实际上应该是两个hashset。

整体的时间复杂度是(NlogN + NlogP)，N为alarms的个数，P为Priority的个数，NlogN是排序的复杂度，NlogP是后面统计处理的时候的复杂度。至于这个集合既需要做key-value的查询，又需要找最大值，那么自然是HashHeap。这种数据机构，我们会在《九章算法强化班》中讲解。

这种算法的名字叫做：扫描线算法。是Google的大爱。

类似的题目是这题，也是Google出过的题：
http://www.lintcode.com/en/problem/building-outline/

Read full article from Google – Remove Alarm