Merge Overlap Interval

#include <iostream>
#include <vector>
#include <utility>


void PrintArr(const std::vector<int>& arr, bool isBreakLine = true)
{
    for (const auto& i : arr)
    {
        std::cout << i << " ";
    }

    if (isBreakLine)
        std::cout << "\n";
}

void Swap(int* num1, int* num2)
{
    int tmp = *num1;
    *num1 = *num2;
    *num2 = tmp;
}

/*  Merge Overlapping Interval
    [6,10], [7,9]
*/

bool CheckOverlapping(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
    bool ret = false;

    if (arr1[0] <= arr2[0])
    {
        if (arr2[0] <= arr1[1])
            ret = true;
    }
    else
    {
        if (arr1[0] <= arr2[1])
            ret = true;
    }

    return ret;
}

std::vector<int> MergeInterval(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
    std::vector<int> mergeInterval(2, 0);

    mergeInterval[0] = (arr1[0] <= arr2[0]) ? arr1[0] : arr2[0];
    mergeInterval[1] = (arr1[1] >= arr2[1]) ? arr1[1] : arr2[1];

    return mergeInterval;
}

std::vector<std::vector<int>> PairInterval(const std::vector<std::vector<int>>& arr1, const std::vector<std::vector<int>>& arr2)
{
    std::vector<std::vector<int>> ret;

    if (arr1.size() == 1 && arr2.size() == 1)
    {
        if (arr1[0][0] > arr2[0][0])
        {
            ret.emplace_back(arr2[0]);
            ret.emplace_back(arr1[0]);
        }
        else
        {
            ret.emplace_back(arr1[0]);
            ret.emplace_back(arr2[0]);
        }

        return ret;
    }

    int i = 0, j = 0;

    while (i < arr1.size() && j < arr2.size())
    {
        if (arr1[i][0] < arr2[j][0])
        {
            ret.emplace_back(arr1[i]);
            i++;
        }
        else
        {
            ret.emplace_back(arr2[j]);
            j++;
        }
    }

    for (int m = i; m < arr1.size(); m++)
    {
        ret.emplace_back(arr1[m]);
    }

    for (int n = j; n < arr2.size(); n++)
    {
        ret.emplace_back(arr2[n]);
    }

    return ret;
}


std::vector<std::vector<int>> SortInterval(std::vector<std::vector<int>>& intervals)
{
    if (intervals.size() == 1)
        return intervals;

    int mid = intervals.size() / 2;

    std::vector<std::vector<int>> leftIntervals(intervals.begin(), intervals.begin() + mid);
    std::vector<std::vector<int>> rightIntervals(intervals.begin() + mid, intervals.end());

    auto leftRet = SortInterval(leftIntervals);
    auto rightRet = SortInterval(rightIntervals);

    auto pairRet = PairInterval(leftRet, rightRet);

    return pairRet;
}

/*
Idea: Tìm phần tử nhỏ nhất sau mỗi lần lặp
*/
void SelectionSort(std::vector<int>& unsorted_arr)
{
    for (int i = 0; i < unsorted_arr.size(); i++)
    {
        int curMin = unsorted_arr[i];
        int newIdxMin = -1;

        for (int j = i + 1; j < unsorted_arr.size(); j++)
        {
            if (unsorted_arr[j] < curMin)
            {
                newIdxMin = j;
                curMin = unsorted_arr[j];
            }
        }

        if (newIdxMin != -1)
            Swap(&unsorted_arr[i], &unsorted_arr[newIdxMin]);
    }
}


int main()
{
    std::vector<std::vector<int>> originInterval = {{1,3},{2,6},{8,10},{15,18}};
    std::vector<std::vector<int>> originInterval1 = {{7, 9}, {6,10}, {4, 5}, {1, 3}, {2, 4}};

    auto sortedIntervals = SortInterval(originInterval);


    for(const auto& interval : sortedIntervals)
    {
        std::cout << "interval:{" << interval[0] << ", " << interval[1] << "} ";
    }

    std::cout << std::endl;

    int idxNonOverlapInterval = 0;
    for (int i = 1; i < sortedIntervals.size(); i++)
    {
        if (CheckOverlapping(sortedIntervals[idxNonOverlapInterval], sortedIntervals[i]))
        {
            sortedIntervals[idxNonOverlapInterval] = MergeInterval(sortedIntervals[idxNonOverlapInterval], sortedIntervals[i]);
        }
        else
        {
            idxNonOverlapInterval++;
            sortedIntervals[idxNonOverlapInterval] = sortedIntervals[i];
        }
    }

    for (int j = 0; j <= idxNonOverlapInterval; j++)
    {
        std::cout << "ret: {" << sortedIntervals[j][0] << ", " << sortedIntervals[j][1] << "} ";
    }

    std::cout << std::endl;



    //---------------------------------------------------------------------------------------
    std::vector<int> unsorted_arr = {11, 4, 27, 34, 43, 17, 13, 17, 31, 12};
    SelectionSort(unsorted_arr);
    PrintArr(unsorted_arr);
}