常规的merge interval question是众所周知的 - 并且具有O（nLogn）解决方案。但是，最近我被问到一个跟进问题 - 如果我们在开始和结束时间值上有一个上限怎么办？我们可以改善运行时吗？即 - 假设开始/结束时间可以具有最大值C.
如果在C已知时可以改善运行时间，那么你可以在O（n）中搜索C并且即使你不知道C也会更快，对吗？我认为，如果你有一个额外的成本，例如，只有整数可以作为间隔限制，你可以改善运行时间。