algorithm - 段区间搜索

Question

我们有一组间隔 [angle1,angle2]。我想找出位于最大间隔数中的 theta [-180,180] 的最佳值。 theta 的值可以是 float 。我尝试使用线性搜索并检查所有间隔，但由于 theta 的值可以是 float ，我认为即使是二分搜索也行不通。

Answer 1

将间隔开始和结束值排序到单个列表中，每个列表都有相应的“S”或“E”值。

扫描列表，当你击中 S 时递增一个计数器，当你击中 E 时递减一个计数器。如果计数器高于目前看到的最高值，请记住该段的 S 和 E 值。

对于环绕的情况，只需将每个环绕的区间(即 angle2 < angle1)分成两部分，一个在零的两边。将 [angle1,360] 和 [0,angle2] 作为新间隔添加到起始集中。