有一堆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使用的也是这种算法。
Read full article from Google – Remove Alarm
No comments:
Post a Comment