Алгоритм для решения проблемы генетического кроссовера

Question

У меня есть список объектов, таких как:

class PairingStrand
{
   int startInt; // the start pos
   int endInt;   // the end pos
   int Index;    // the index of pairing
   int Strand;   // Strand is either "5" or "3"
}

Каждая позиция (целое число) может быть связана только с одним объектом.

Объект с Strand = 5 соединяется с объектомс такими же «индексами» и strand = 3.

. Список упорядочен по «startInt» каждого объекта.Таким образом, различные области спаривания могут пересекаться друг с другом.

«ПЕРЕКРЫТИЕ» означает, что два региона перекрываются, но если один регион достаточно велик, чтобы полностью охватить другой, он не считается «ПЕРЕКРЕТНЫМ».

Например ...

{10~15 : 40~45} (startInt ~ endInt : startInd ~ endInx) 

пересекается с

{20~30 : 60~70}

Однако

{10~15 : 40~45} 

не считается пересекающимсяс

{20~25: 30~35}

Мой вопрос заключается в том, как определить самый большой блок, у которого нет пересечения с другими блоками в списке. Пересечение разрешено внутриблок.(Другими словами, «переход» разрешен, но не обязателен внутри блока, хотя он не разрешен между блоками)

Возможно, я не очень четко описал вопрос.Вот простой пример:

Список, как показано ниже:

obj1 (10~20, index 1, strand 5)
obj2 (25~30, index 2, strand 5)
obj3 (31~32, index 4, strand 5)
obj4 (33~34, index 4, strand 3)
obj5 (35~45, index 1, strand 3)
obj6 (50~55, index 2, strand3)
obj7 (60~80, index 3, strand 5)
obj8 (90~110, index 3, strand 3)

После обработки функция должна вернуть блок, состоящий из (obj1 ~ obj6).

Заранее спасибо.

Answer 1

Псевдокод:

Dictionary<Index, Pairing> openPairings;
List<Index> possibilities;

foreach(pairing)
{
    if(openPairings.ContainsKey(pairing.Index))
    {
        // This is the closing of the pair
        // When there are no other open strands at the time of closing,
        // AND the pairing was in the possibilities list, it could be the largest
        if(possibilities.Contains(pairing.Index))
        {
            // The opening entry: openPairings[pairing.Index]
            // The closing pairing: pairing
            // Do your size check here to find the largest
        }
        openPairings.Remove(pairing.Index);
    }
    else
    {
        // This is the opening of the pair
        // There must be no other open pairings or there will be an overlap OR
        // the outer pairing is larger anyway, as it completely engulfs this pairing
        if(openPairings.IsEmpty)
            possibilities.Add(pairing.Index);
        openPairings.Add(pairing.Index, pairing);
    }
}