文本選擇交叉算法

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 
}