在C ++中合并重叠的间隔解决方案

给您一个间隔的集合，合并所有重叠的间隔。

Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

该问题可以通过两种方式解决：

1. 蛮力法
2. 通过对输入数组进行排序

1.蛮力法

在这种方法中，从第一个间隔开始，我们将与所有其他间隔进行比较以进行重叠。如果发现重叠，则我们合并这些间隔并继续检查下一个元素。

2.通过对输入数组进行排序。

首先，我们对输入数组进行排序。

然后，我们将第一个元素添加到“ result_set”中。然后，如果下一个间隔在上一个间隔结束之后开始，则它们不会相互重叠。

我们将通过在代码后输入以下内容来查看通行证：

C ++解决方案

    
#include<iostream>
#include<vector>

using namespace std;

struct Interval 
{
    int start;
    int end;
};

/*Merge Intervals Using Brute force START */

bool check_is_intersection(Interval &int1, Interval &int2)
{
    if(int1.end<int2.start || int2.end<int1.start) return false;
    return true;
}

void mergeIntervalsToFirst(Interval &int1, Interval &int2)
{
    if(int1.start>int2.start) int1.start=int2.start;
    if(int1.end<int2.end) int1.end=int2.end;
}

vector<Interval> merge_using_brute_force(vector<Interval> &intervals) 
{
    vector<Interval> result_set;
    if(intervals.size()==0) return result_set;

    int total_intervals_length = intervals.size();
    bool isMerge=false;
    for(int outer_loop = 0; outer_loop < total_intervals_length; ++outer_loop)
    {
        // Insert the first pair into the result set
        if(outer_loop==0)
        { 
            result_set.push_back(intervals[0]);
        }
        else
        {
            // from the second pair, check if there is possibility of overlapping

            int length_of_result_set = result_set.size();
            for(int inner_loop = 0; inner_loop < length_of_result_set; ++inner_loop)
            {
                if(check_is_intersection(result_set[inner_loop], intervals[outer_loop]))
                {
                    // if we found an overlapping element, then merge those two pairs
                    mergeIntervalsToFirst(result_set[inner_loop], intervals[outer_loop]);

                    //Check for remaining intervals pairs to be overlapped inside the result set.
                    vector<Interval>::iterator iter=result_set.begin()+inner_loop+1;
                    while(iter!=result_set.end())
                    {
                        if(check_is_intersection(result_set[inner_loop], *iter))
                        {
                            mergeIntervalsToFirst(result_set[inner_loop], *iter);
                            result_set.erase(iter);
                        }
                        else 
                            ++iter;
                    }
                    isMerge=true;        
                    break;
                }
            }

            // If the present interval[outer_loop] is not merged with any other interval, then it means that it didnt overlap.
            // Hence Push the interval into the result set.
            if(!isMerge) 
            {   
                result_set.push_back(intervals[outer_loop]);
            }
            else 
            {
                // reset the value
                isMerge=false;
            }
        }
    }
    return result_set;
}
/*Merge Intervals Using Brute force END */

/*Merge Intervals Using sorting START */

static bool comp(const Interval& a, const Interval& b)
{
    return a.start < b.start;
}
vector<Interval> merge_using_sort_method(vector<Interval> &intervals) 
{
    vector<Interval> result_set;
    if(intervals.empty())
    {
        return result_set;
    }

    sort(intervals.begin(), intervals.end(), comp);

    result_set.push_back(intervals[0]);


    for (int i = 1; i < intervals.size(); i++) 
    {
        if (result_set.back().end < intervals[i].start) 
            result_set.push_back(intervals[i]);
        else
            result_set.back().end = max(result_set.back().end, intervals[i].end);
    }
    return result_set;
}


/*Merge Intervals Using sorting END */


int main() 
{

    vector<Interval> itv = { {1,3}, {8,10},{2,6},  {15,18} };
    //vector<Interval> result = merge_using_brute_force(itv) ;
    vector<Interval> result = merge_using_sort_method(itv) ;
    for (auto &i : result)
        cout << i.start << ' ' << i.end << endl;

}

输出：

1 6
8 10
15 18

使用蛮力方法跟踪输出：

Input Set
{1,3}, {8,10}, {2,6}, {15,18}

result_set = NULL
Pass 1:
	outer_loop = 0 to 3
Hence add {1, 3} to result set.

result_set = {1, 3}
Pass 2:
	outer_loop = 1 to 3
	length_of_result_set = 1

		inner_loop = 0 to 1
			check_is_intersection(result_set[0], intervals[1])
				false
	enter the interval at intervals[1] into result set.

result_set = {1, 3}, {8,10}
Pass 3:
	outer_loop = 2 to 3
	length_of_result_set = 2

		inner_loop = 0 to 2
			check_is_intersection(result_set[0], intervals[2])
				true
				mergeIntervalsToFirst({1, 3}, {2, 6}) => {1, 6}

				Check if any other intervals inside the result set is an overlap.
				while (result_set[1] to 1)
					check_is_intersection({1, 6}, {8, 10})
					false

result_set = {1, 6}, {8,10}
Pass 4:
	outer_loop = 3 to 3
	length_of_result_set = 2

		inner_loop = 0 to 2
			check_is_intersection(result_set[0], intervals[3])
				false
			
			enter the interval at intervals[3] into result set.

Final result ={1, 6}, {8,10}, {15, 18}

使用排序方法跟踪输出

Input Set
{1,3}, {8,10}, {2,6}, {15,18}

First step is to sort all the intervals. After sorting, below will be the intervals.


Input Set
{1,3}, {2,6}, {8,10}, {15,18}

Add the first interval to result set

result_set = {1, 3}

result_set = {1, 3}
Pass 1:
	for 1 to 3

	if (result_set.back().end < intervals[i].start) => (3 < 2)

		false, Hence merge
		Hence result_set.back().end = max(result_set.back().end, intervals[i].end);
									= max(3, 6)
									= 6

result_set = {1, 6}
Pass 2:
	for 2 to 3

	if (result_set.back().end < intervals[i].start) => (6 < 8)

		true, add {8, 10} to reslut set

result_set = {1, 6}, {8, 10}
Pass 3:
	for 3 to 3

	if (result_set.back().end < intervals[i].start) => (8 < 18)

		true, add {15, 18} to reslut set


Final result ={1, 6}, {8,10}, {15, 18}

请在本文的评论部分中写下您的答案。

该网站上可用的教程列表：