Слияние двух групп

Question

У меня много групп, у каждой группы есть минимальный и максимальный диапазон, в который они могут вписаться. эти диапазоны перекрываются между различными группами

Например,

    Group1  Min Range 3.125 , Max Range 3.5
    Group2  Min Range 3.25 , max Range 3.75
    Group 3 Min Range 3.5, max range 4.0

Мне нужно объединить эти группы, чтобы сформировать группы с минимальным количеством.

Как

Group1  Min Range 3.125 , Max Range 3.5
              Item 1 value 3.125
              Item 2 value 3.3
              Item 3 value 3.5

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.3

Я могу объединить эти две группы в Группу 1.

Это то, что я делаю

for( size_t TopIndex = 0; TopIndex < GroupVector.Size(); TopIndex++)
{
    Group& CurrentGroup = GroupVector[TopIndex];
    for( size_t InnerIndex = TopIndex +1; InnerIndex < GroupVector.Size(); InnerIndex++)
    {
        Group& InnerGroup  = GroupVector[InnerIndex];
        MergeGroup(CurrentGroup,InnerGroup);
    }
}

В MergeGroup,

1.  Move items from Group 1 to Group 2 , Save total number of group after merge (I will stop if number of group is 1)
2.  Move items from Group 2 to Group 1 , Save total number of group after merge
3.  Compare number of group form step 1 &2  and accept an option which results in less number of groups.

У меня большое количество групп для слияния, и я пытаюсь выяснить, есть ли лучший способ сделать это.

Answer 1

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

Exemple:

group1 min 1.00, max 2.00
group2 min 1.50, max 2.50
group3 min 1.25, max 2.25

все элементы группы 3 можно объединить в группы 2 и 3.

Это будет первое минимальное сокращение. Тогда я бы проверил пункт на других группах

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.30
              Item 3 value 3.50

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.30

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

с алгоритмом проверки возможности объединения элементов в следующие группы что-то вроде:

foreach (groups as group){
    foreach(group.items as item){
        tryToInsertItemIntoOtherGroups(item);
        if(group is empty){
            delete groupe;
        }
    }
}

первый цикл (для первой группы) изменится так:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.30
              Item 3 value 3.30
              Item 4 value 3.50

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

второй цикл (для второй группы) приведет к удалению группы 2:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.25
              Item 3 value 3.30
              Item 4 value 3.30
              Item 5 value 3.50

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

третий цикл (для третьей группы) приведет к удалению группы 3:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.25
              Item 3 value 3.30
              Item 4 value 3.30
              Item 5 value 3.50
              Item 6 value 3.40
              Item 7 value 3.50