algorithm-examples/cpp-algorithm/src/sort/merge_interval.h at main · codejsha/algorithm-examples · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#ifndef CPP_ALGORITHM_MERGE_INTERVAL_H
#define CPP_ALGORITHM_MERGE_INTERVAL_H

#include <algorithm>
#include <vector>

namespace MergeInterval
{
    /**
     * \brief Merge intervals if they overlap.
     * \details Given a collection of intervals, merge all overlapping intervals.
     * \param intervals intervals to be merged
     * \return merged intervals
     */
    std::vector<std::vector<int>> MergeIntervals(
        std::vector<std::vector<int>>& intervals);

    /**
     * \brief Merge intervals if they overlap.
     * \details Given a collection of intervals, merge all overlapping intervals.
     * \param intervals interval collection
     * \param new_interval new interval to be merged
     * \return merged intervals
     */
    std::vector<std::vector<int>> MergeIntervals(
        std::vector<std::vector<int>>& intervals,
        std::vector<int> new_interval);
}

// ----------------------------------------------------------------------------
inline std::vector<std::vector<int>> MergeInterval::MergeIntervals(
    std::vector<std::vector<int>>& intervals)
{
    // if array is empty
    if (intervals.empty())
    {
        return {};
    }

    // sort intervals by start time
    std::ranges::sort(intervals, [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    std::vector<std::vector<int>> result;
    result.emplace_back(intervals[0]);
    intervals.erase(intervals.begin());

    for (const auto& interval : intervals)
    {
        // if current interval does not overlap with previous
        if (result.back()[1] < interval[0])
        {
            result.emplace_back(interval);
        }
        else
        {
            result.back()[1] = std::max(result.back()[1], interval[1]);
        }
    }

    return result;
}

// ----------------------------------------------------------------------------
inline std::vector<std::vector<int>> MergeInterval::MergeIntervals(
    std::vector<std::vector<int>>& intervals,
    std::vector<int> new_interval)
{
    std::vector<std::vector<int>> result;
    int idx = 0;

    // add all intervals starting before new_interval
    while (idx < static_cast<int>(intervals.size()) && intervals[idx][1] < new_interval[0])
    {
        result.emplace_back(intervals[idx]);
        ++idx;
    }

    // merge all overlapping intervals to one considering new_interval
    while (idx < static_cast<int>(intervals.size()) && intervals[idx][0] <= new_interval[1])
    {
        new_interval[0] = std::min(intervals[idx][0], new_interval[0]);
        new_interval[1] = std::max(intervals[idx][1], new_interval[1]);
        ++idx;
    }
    result.emplace_back(new_interval);

    // add all intervals starting after new_interval
    while (idx < static_cast<int>(intervals.size()))
    {
        result.emplace_back(intervals[idx]);
        ++idx;
    }

    return result;
}

#endif