The Algorithm Design Manual (3rd) Exercise Solution 'E4-14'

Table of Contents

Introduction
Repository
Exercise 4-14
- Question
- Solution
  - Outline
  - Code

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-14

Question

Given a list I of n intervals, specified as $(x_i, y_i)$ pairs, return a list where the overlapping intervals are merged. For $I = \{(1, 3),(2, 6),(8, 10),(7, 18)\}$ the output should be $\{(1, 6),(7, 18)\}$ . Your algorithm should run in worst-case $O(n log n)$ time complexity.

Solution

Outline

Sort the coordinates of endpoints with Labeling 'start' and 'end'.
    order: ascending for coordinate and the way 'start' ends are always
        precede to 'end' ends.

Traverse the newly created array and record intervals.
    How to pick the ends of new interval:
        Select the start end.
        Count   +1 when encountering 'start' end
                -1 when encountering 'end' end
        If counter becomes 0, Create new interval and continue to find
        another new intwerval.

Code

/*
    Sort the coordinates of endpoints with Labeling 'start' and 'end'.
        order: ascending for coordinate and the way 'start' ends are always
            precede to 'end' ends.

    Traverse the newly created array and record intervals.
        How to pick the ends of new interval:
            Select the start end.
            Count   +1 when encountering 'start' end
                    -1 when encountering 'end' end
            If counter becomes 0, Create new interval and continue to find
            another new intwerval.

*/
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

struct Interval {
    int cd_start;
    int cd_end;
    friend bool operator==(const Interval& itv1, const Interval& itv2) {
        return itv1.cd_start == itv2.cd_start && itv1.cd_end == itv2.cd_end;
    }
};

std::vector<Interval> merge_intervals(const std::vector<Interval>& itvs) {
    enum InvEnds { stt = 1, end = -1 };
    std::vector<std::pair<int, InvEnds>> labeled_ends;
    // parse
    for (const auto& itv : itvs) {
        labeled_ends.push_back({itv.cd_start, InvEnds::stt});
        labeled_ends.push_back({itv.cd_end, InvEnds::end});
    }
    // sort
    std::sort(labeled_ends.begin(), labeled_ends.end(),
              [](const auto& a, const auto& b) {
                  if (a.first != b.first) return a.first < b.first;
                  return a.second > b.second;
              });
    // traverse
    std::vector<Interval> merged;
    bool flaged = false;
    unsigned int cnt{0};
    int cd_start;
    for (auto it{labeled_ends.cbegin()}; it != labeled_ends.cend(); it++) {
        if (!flaged) {
            cd_start = it->first;
            flaged = true;
        }
        cnt += static_cast<int>(it->second);
        if (!cnt) {
            merged.push_back({cd_start, it->first});
            flaged = false;
        }
    }
    return merged;
}

int main(int argc, char const* argv[]) {
    assert(merge_intervals({Interval{-3, 3}, Interval{5, 15}}) ==
           (std::vector{Interval{-3, 3}, Interval{5, 15}}));
    assert(merge_intervals({Interval{-3, 5}, Interval{5, 15}}) ==
           (std::vector{Interval{-3, 15}}));
    assert(merge_intervals({Interval{-3, 8}, Interval{5, 15}}) ==
           (std::vector{Interval{-3, 15}}));
    assert(merge_intervals({Interval{5, 5}, Interval{5, 15}}) ==
           (std::vector{Interval{5, 15}}));
    assert(merge_intervals({Interval{10, 15}, Interval{5, 15}}) ==
           (std::vector{Interval{5, 15}}));
    assert(merge_intervals({Interval{10, 17}, Interval{5, 15}}) ==
           (std::vector{Interval{5, 17}}));
    assert(merge_intervals({Interval{15, 17}, Interval{5, 15}}) ==
           (std::vector{Interval{5, 17}}));

    assert(merge_intervals({Interval{1, 3}, Interval{2, 6}, Interval{8, 10},
                            Interval{7, 18}}) ==
           (std::vector{Interval{1, 6}, Interval{7, 18}}));

    return 0;
}