文本选择交叉算法

Question

我有一个网站，允许多个用户突出显示html文档（主要是文本）的多个部分。

每个高光标记由开始，字符位置，长度和用户ID标记。

我需要找出最突出显示的部分（最重叠部分），但不同的用户可能没有相同的开始和结束位置。实现这种功能的最佳方式是什么？最好在c＃

Answer 1

把所有用户的开始和结束选择放在一个列表中，排序。从列表顶部开始，为您找到的每个开始点增加一个计数器，为您找到的每个终点递减。计数器的最高值是文本的最高亮/最重叠部分的开始。列表中的下一项是该选择的结尾。

Answer 2

这应该将您的数据转换为dthorpe算法所需的结构。如果我有更多的时间，我可能可能是Linq，如果剩下的话。

更新：好的，现在完成（如果还没有测试....） 更新2：现在，实际测试&工作！

// Existing data structure 
class StartLen 
{ 
    public int Start {get; set;} 
    public int Len {get; set;} 
    public string UserId {get; set;} 
} 

// Needed data struct 
class StartEnd 
{ 
    public int Pos {get; set;} 
    public bool IsStart {get; set;} 
} 

class Segment 
{ 
    public int Start { get; set; } 
    public int End { get; set; } 
    public int Count { get; set; } 
}  

int count = 0, lastStart = -1; // next rev, I figure a way to get rid of these. 

// this can't be a lambda, it has to be a real function 
IEnumerable<StartEnd> SplitSelection(StartLen sl) 
{ 
    yield return new StartEnd() {Pos = sl.Start, IsStart = true} ; 
    yield return new StartEnd() {Pos = sl.Start+sl.Len -1 , IsStart = false} ; 
} 

List<StartLen> startLen = new List<StartLen>(); 
// we fill it with data for testing 
// pretending to be the real data 
startLen.Add(new StartLen() { Start=10, Len=10, UserId="abc123" }); 
startLen.Add(new StartLen() { Start=15, Len=10, UserId="xyz321" }); 

var mostSelected = 
    startLen.SelectMany<StartLen, StartEnd>(SplitSelection) 
     .OrderBy(se=>se.Pos) 
     .Select(se=> 
     { 
      if (se.IsStart) 
      { 
       lastStart = se.Pos; 
       count++; 
      } 
      else 
      { 
       count--; 
       if (lastStart > 0) 
       { 
        var seg = new Segment 
         { Start = lastStart, End = se.Pos, Count = count }; 
        lastStart = -1; 
        return seg; 
       } 
      } 
      // Garbage, cuz I need to return something 
      return new Segment { Start = 0, End = 0, Count = -1 }; 
     }) 
     .OrderByDescending(seg => seg.Count) 
     .First(); 

// mostSelected holds Start & End positions 
}