http://www.1point3acres.com/bbs/thread-175972-1-1.html
http://www.1point3acres.com/bbs/thread-173794-1-1.html
| 3. 火星上有1百万个sensor，每个sensor独立工作，某个sensor检测到一个事件后会返回地球一个时间戳， 对于同一个sensor来说是按照时间顺序返回的，但每个sensor之间不是同步工作的。 如果所有sensor都在同一个时间戳有反馈，则叫做有趣的事件。求最早的有趣事件。(g家面试题） 这一题就是在排序好的数组中找第一个重合点，求问好一点的算法是什么？ |
http://www.1point3acres.com/bbs/thread-173794-1-1.html
n houses, k colors. neighboring houses cannot be painted with the same color.
NOTICE: neighboring relationship is given by adjacent list which means a house may have multiple neighbors.
基本上是图的着色问题。讨论的时候那个帖子楼主说思路是这样的：
“看做一个graph。然后分组。初始所有house都为group 0
用bfs遍历这个图。然后根据相邻house颜色不一样改变组号。。。
最后颜色根据cost排序，然后最大group的house涂cost最小的颜色，以此类推”
CSP (constraint satisfaction problem). 可以用DFS解。。然后可以加上heuristic ： 比如先给周围邻居最多的染色。。
也还有很多别的优化：http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf
也还有很多别的优化：http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf
有两个思路吧，第一个是用welch powell方法，按照图上每个节点的度按照降序排列，然后从第一个节点涂色，然后找后面和这个点不相邻的点都归为一类，这样就可以将所有点分类，但是按照某些testcase他是没法分类到最优解的
basic idea基本就是找入度最小的node， 从图中移除， 放到一个stack里，然后recursive的这样做，当然iterative的也行。最后按照stack的node顺序来着色。
可以参考一下Chaitin-Briggs's graph coloring algorithm, 没有那么复杂，不过对于着色问题值得看一下
