Buckle practice - 30 set the intersection size to at least 2

30 Set the intersection size to at least 2

1. Problem description
An integer interval [a, b] ( a < b ) It's about starting from a To b All consecutive integers of , Include a and b.

Give you a set of integer intervals intervals, Please find a minimum set S, bring S Elements and intervals in intervals Every integer interval in has at least 2 Elements intersect .

Output this minimal set S Size .

Example 1:

Input : intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]

Output : 3

explain :

Consider the set S = {2, 3, 4}. S And intervals All four intervals in have at least 2 Intersecting elements .

And this is S In the smallest case , So we export 3.

Example 2:

Input : intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]

Output : 5

explain :

The smallest set S = {1, 2, 3, 4, 5}.

The following can be used: main function ：

int main()

{

int m,n,data;

vector<vector<int> > intervals;

cin>>m;

for(int j=0; j<m; j++)

{

    vector<int> aRow;

    for(int i=0; i<2; i++)

    {

        cin>>data;

        aRow.push_back(data);

    }

    intervals.push_back(aRow);

}



int res=Solution().intersectionSizeTwo(intervals);

cout<<res;



return 0;

}
2. Enter description
First type intervals The number of intervals of m（ The scope is [1, 3000]）,

Then input m That's ok , Each row 2 A digital （ [0, 10^8] Range of integers ）, Represents the left of the interval 、 Right border .
3. The output shows that
Output an integer
4. Example
Input
4
1 2
2 3
2 4
4 5
Output
5
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<stack>
using namespace std;

bool cmp(vector<int>&a, vector<int> &b)// Define a comparison function , Pay attention to the writing of parameters here 
{
    
	return a[1]<b[1]||(a[1]==b[1]&&a[0]>b[0]);// First according to   The second element   Ascending comparison  , Press if equal   First element   Descending 
}

int intersectionSizeTwo(vector<vector<int> > &intervals)
{
    
	//1. First, in ascending order according to the right endpoint , Left endpoint descending 
	sort(intervals.begin(), intervals.end(), cmp);
	
	//2. Define the initial result array 
	vector<int>v{
     -1,-1 };

	//3. Traverse 
	for (auto val : intervals)
	{
    
		int len = v.size();
		if (val[0] <= v[len - 2]) continue;// There must be two repeating elements , So there are two repetitions without adding elements 
		if (val[0] > v.back()) 
			v.push_back(val[1] - 1);// explain v There is no intersection between the array and the current interval , So here we add the two largest elements 
		v.push_back(val[1]);
	}
	return v.size()-2;
}


 
int main()

{
    

	int m, n, data;

	vector<vector<int> > intervals;

	cin >> m;

	for (int j = 0; j < m; j++)

	{
    

		vector<int> aRow;

		for (int i = 0; i < 2; i++)

		{
    

			cin >> data;

			aRow.push_back(data);

		}

		intervals.push_back(aRow);

	}

	int res = intersectionSizeTwo(intervals);

	cout << res<<endl;

	return 0;
}