3323. Minimize Connected Groups by Inserting Interval

You are given a 2D array intervals, where intervals[i] = [starti, endi] represents the start and the end of interval i. You are also given an integer k.

You must add exactly one new interval [startnew, endnew] to the array such that:

• The length of the new interval, endnew - startnew, is at most k.
• After adding, the number of connected groups in intervals is minimized.

A connected group of intervals is a maximal collection of intervals that, when considered together, cover a continuous range from the smallest point to the largest point with no gaps between them. Here are some examples:

• A group of intervals [[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps.
• However, a group of intervals [[1, 2], [3, 4]] is not connected because the segment (2, 3) is not covered.

Return the minimum number of connected groups after adding exactly one new interval to the array.

class Solution {
public:
    int minConnectedGroups(vector<vector<int>>& intervals, int k) {
        vector<vector<int>> A;
        sort(begin(intervals), end(intervals));
        for(auto& i : intervals) {
            if(A.size() == 0 or A.back()[1] < i[0]) A.push_back(i);
            else A.back()[1] = max(A.back()[1], i[1]);
        }
        int n = A.size(), res = n;
        for(int i = 0, j = 0; i < n; i++) {
            while(j < n and A[j][0] <= A[i][1] + k) j++;
            res = min(res, i + 1 + n - j);
        }
        return res;
    }
};