小编Lan*_*lds的帖子

我最近被问到关于以下问题的编码问题.我有一些解决这个问题的方法,但我不确定这些问题是否最有效.

问题:

编写程序来跟踪文本范围集.起点和终点将是字符串.

Text range example : [AbA-Ef]
 Aa would fall before this range
 AB would fall inside this range
 etc.

字符串比较就像'A'<'a'<'B'<'b'...'Z'<'z'

我们需要支持此范围内的以下操作

• 添加范围 - 如果适用,这应合并范围
• 删除范围 - 这将从跟踪的范围中删除范围并重新计算范围
• 查询范围 - 给定一个字符,函数应该返回它是否是任何跟踪范围的一部分.

请注意,跟踪范围可以是不连续的.

我的解决方案

我提出了两种方法.

1. 将范围存储为双向链表或
2. 将范围存储为某种平衡树,叶节点具有实际数据,并且它们作为链表相互连接.

您认为这个解决方案是否足够好,或者您可以考虑采用更好的方法来实现这三个API,从而提供最佳性能？