Merging Intervals

sort(a.begin(), a.end());
vector<pair<int, int> > res;
for (int i = 0; i < n; ++i) {
    int l = 0, r = res.size() - 1;
    
    while (l < r) {
        int mid = (l + r) >> 1;
        if (res[mid].second >= a[i].first) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    
    if (l < (int)res.size() and res[l].second >= a[i].first) {
        res[l].first = min(res[l].first, a[i].first);
        res[l].second = max(res[l].second, a[i].second);
    } else {
        res.push_back(a[i]);
    }
}
	
cout << res.size() << '\n';

Description

Given several intervals, u are asked the number of intervals if all intervals are merged. We can merge two intervals if they have overlapping parts.

Greedy & binary_search

1.First sort the intervals by left endpoint first.
2.Add intervals into an container one by one, every time check if there exist an interval overlapping the one now adding, if it is, modify the interval into a bigger one, else simply add it. I use binary search to check it.