时间轮首先是一个“轮”, 即环形数组. 就像手表一样, 用 buckets[] 代表刻度, 以 tick 为单位递进增加时间, 触发对应 bucket 上的任务, 以此无限循环.
每圈时间轮会经过 interval = tickMs * bucketSize 的时间间隔, 对于超过时间间隔的任务, 基本有两种实现方式----多层时间轮和单层复用时间轮.
多层时间轮通过增加上级时间轮的方式来应对 delay 超过 interval 的情况. 下层时间轮每经过一圈, 就将上层时间轮推进一个 tick. 如果上层时间轮的任务被触发, 就放入到下层时间轮中, 直到在最底层时间轮被触发.
本文中, 英文部分均来自于原文摘抄, 如果想要更好的理解和阅读体验, 请不要忽略英文引用!
Effective Java 这本书作为 Java 编程思想和范式的"集大成者", 需要很深的 Java 编程功底. 我在阅读时也感受到很多没有了解过的东西, 尤其是读英文原著, 感觉一些部分的理解尚且非常浅薄, 尤以 Stream API 的部分为甚.
现在只是第一遍阅读这本书的原版, 只在博客中做粗略的记录和思考. 在读完第一遍之后, 会再次进行巩固和更新.
对于区间问题, 我们还是首先将其按照某一侧端点排序, 这里我们选择左端点.
我们记录每个已选择区间分组的最大右端点 maxR 的值, 从左到右遍历排序后的区间 range.
同样的, 我们先将所有区间按照右端点大小从小到大排序. 从右端点最小的区间开始选取, 如果下一个区间包含了当前选取区间的右端点, 就跳过; 如果不包含, 就选取.
对于此类区间问题, 可以将区间根据左/右端点排序, 然后遍历讨论.
本题中, 我们要选择尽量少的点, 就要让我们选的点尽量覆盖多个区间. 对区间根据右端点排序后, 从最左侧的区间开始, 如果我们期望选点尽量覆盖多的区间, 就应该选择当前区间最右侧的点.
