C ++ сортировка интервалов, структура, а также удаление перекрывающихся интервалов

Question

Здесь интервалы такие же, как у линии. Хотя я нашел правильное решение для двух целей:

1) интервалы сортировки;

2) отклонить при добавлении интервалов, перекрывающихся с существующими.

struct Line {
    int down;
    int up;

    Line(int down, int up) {
        this->down = down;
        this->up = up;
    }
};

int main() {
    auto cmp = [] (const Line& a, const Line& b) {//NOTE: this can even detect the intersection, as well as sort the interval!!
        if (a.up <= b.down) return true;
        else return false;
    };

    set<Line, decltype(cmp)> s(cmp);
    Line l1{2, 3};
    Line l2{3, 5};
    Line l3{1, 2}; //success for insertion
    Line l4{4, 6}; //fail for insertion b/c of insersection


    auto ret = s.insert(l2);
    cout << "insert 3->5 ";
    if (ret.second) cout << "success " << endl;
    else cout << "fail " << endl;

    ret = s.insert(l3);
    cout << "insert 1->2 ";
    if (ret.second) cout << "success " << endl;
    else cout << "fail " << endl;

    ret = s.insert(l1);
    cout << "insert 2->3 ";
    if (ret.second) cout << "success " << endl;
    else cout << "fail " << endl;

    ret = s.insert(l4);
    cout << "insert 4->6 ";
    if (ret.second) cout << "success " << endl;
    else cout << "fail " << endl;

    return 0;
}

Output:
insert 3->5 success
insert 1->2 success
insert 2->3 success
insert 4->6 fail
set finally contains: 1->2, 2->3, 3->5,

Что-то меня все еще удивляет:

1) Почему простого сравнения a.up <= b.down достаточно для обнаружения перекрывающихся интервалов?

Разве мы не должны делать что-то вроде стандартного подхода к обнаружению перекрытия интервалов?

max(a.down, b.down) < min(a.up, b.up)

2) 3-й шаг мне не понятен

insert 3->5 success
insert 1->2 success //OK, b/c 2 <= 3, a.up <= b.down return true
insert 2->3 success //Why success? 3 > 1, i.e., a.up > b.down, return false; does it only compare with interval 3->5?

3) Почему приведенный ниже код не работает для удаления перекрывающихся интервалов?

    auto cmp_set = [](const Line& a, const Line& b) {
        if (max(a.down, b.down) < min(a.up, b.up)) return 0; //standard way to detect overlapping of intervals
        else { //sort the two intervals 
            if(a.up <= b.down) return -1;
            else return 1;
        }
    };

Answer 1

1) Почему простого сравнения a.up <= b.down достаточно для обнаружения перекрывающихся интервалов? </p>

[a.down, a.up[ перекрытия [b.down, b.up[ при max(a.down, b.down) < min(a.up, b.up), что эквивалентноa.down < b.up && b.down < a.up (помните, что у нас также есть a.down <= a.up && b.down <= b.up из определения интервала).

Мы также можем перечислить возможности:

• a.down < a.up < b.down < b.up (a < b)
• a.down < b.down < a.up < b.up Пересечение
• a.down < b.down < b.up < a.up Пересечение (полностью включено)
• b.down < a.down < a.up < b.up Пересечение (полностью включено)
• b.down < a.down < b.up < a.up Пересечение
• b.down < b.up < a.down < a.up (b < a)

3-й шаг мне не понятен

insert 3->5 success insert 1->2 success //OK, b/c 2 <= 3, a.up <= b.down return true insert 2->3 success //Why success? 3 > 1, i.e., a.up > b.down, return false; does it only compare with interval 3->5?

Line l1{2, 3};
Line l2{3, 5};
Line l3{1, 2};
Line l4{4, 6};

Вставить l1в {l3, l2}

• l1 < l2 поэтому l1 раньше l2
• !(l1 < l3) так что l1 не раньше l3
• l3 < l1 так l1 после l3 -> {l3, l1, l2}

Для l4 в {l3, l1, l2} Имеется:

• !(l4 < l2) (аналогично для l3 и l1), поэтому l4 не до l2
• !(l2 < l4), поэтому l4 не после l2

у нас есть оба !(l2 < l4) && !(l4 < l2), поэтому есть эквивалент , мы не вставляем l4.

3) Почему приведенный ниже код не работает для удаления перекрывающихся интервалов?

Я не понимаю, где вы его используете.