我对这个算法问题有疑问; 我会粘贴问题然后回顾我当前的想法和解决方案.
有N (up to 100,000)定义为线段[(x1, y1), (x2, y2)],其中x1 < x2和y1 < y2(例如线段具有正斜率).即使在端点处,也没有线段接触或交叉.第一部分有(x1, y1) = (0, 0).想象一下,每个部分都是一个人必须攀爬的二维山.
一个人从(0, 0)第一座山开始登陆.每当一个人降落在山坡上时,他就爬到最后,然后(x2, y2)直接向下跳.如果他降落在另一座山上(该段的任何地方),这个过程仍在继续:他爬上那座山并跳起来.如果没有更多的山丘,他就会落入-INFINITY并且过程结束.每个山(x1, y1) -> (x2, y2)都应该被视为包含点(x1, y1)但不包含该点(x2,
y2),以便如果他从上面落在它的位置上x = x1,该人将落在山上,但如果他落在山上,他将不会落在山上上面的x = x2.
目标是计算他接触的山丘数量.
我目前的想法
我正在考虑沿着x轴扫过一条平面线.每个部分由BEGIN和END事件组成; 每当我们遇到线段的开头时,我们将它添加到一个集合中.每次我们遇到线段的结尾时,我们都会从集合中删除它.当我们到达当前山丘的终点时,我们应该检查我们可以降落的最高山丘的集合.但是,我不知道如何快速确定如何检查,因为集合中可能有N个条目.此外,在跳到另一座山之后,这些的顺序将会改变,因为每个段的斜率可能不同,我不知道如何解释这个差异.
有什么想法吗？