Interval greedy (interval merge)

803. Interval Merging

• Title
• Submission History
• Discussion
• Problem Solution
• Video Tutorial

given n

Intervals [li,ri]

, requires merging all intersecting intervals.

Note that if they intersect at the endpoints, there is also an intersection.

Output the number of intervals after the merge is completed.

Example: [1,3]

and [2,6] can be combined into one interval [1,6]

.

Input format

The first line contains the integer n

.

Next n

lines, each line contains two integers l and r

.

Output format

A total of one line, including an integer, indicates the number of intervals after the merge interval is completed.

Data Range

1≤n≤100000

,
−109≤li≤ri≤109

Sample input:

51 2twenty four5 67 87 9

Sample output:

3

Sort by the left endpoint from small to large, then by the right endpoint from small to large, and compare the right endpoint of the previous interval with the left end of the next interval each timePoints, if there is an intersection, they can be merged into a new interval, otherwise they cannot be merged into an interval.

#include #include #include #include using namespace std;typedef pair PLL;void merge(vector &vec) //merge interval{sort(vec.begin(),vec.end()); //By default, the first element is sorted from small to large, and then the second element is sortedvector res;int st=vec[0].first,ed=vec[0].second;;for(int i=1;i> n;vector vec;for(int i=0;i> l >> r;vec.push_back({l,r});}merge(vec);cout << vec.size() << endl;return 0;}