Non-overlapping Intervals Solution

This problem shares similarities with the minimum arrrows to burst balloons problem. Two approaches exist for resolving interval overlaps:

class IntervalSolver {
public:
    static bool sortStart(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    
    int removeOverlaps(vector<vector<int>>& ranges) {
        if (ranges.empty()) return 0;
        sort(ranges.begin(), ranges.end(), sortStart);
        
        int removals = 0;
        for (int idx = 1; idx < ranges.size(); idx++) {
            if (ranges[idx][0] < ranges[idx-1][1]) {
                removals++;
                ranges[idx][1] = min(ranges[idx-1][1], ranges[idx][1]);
            }
        }
        return removals;
    }
};

Alternative approach using end-sorted intervals:

class IntervalCounter {
public:
    static bool sortEnd(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    
    int countNonOverlapping(vector<vector<int>>& ranges) {
        if (ranges.empty()) return 0;
        sort(ranges.begin(), ranges.end(), sortEnd);
        
        int nonOverlapCount = 1;
        int currentEnd = ranges[0][1];
        for (int idx = 1; idx < ranges.size(); idx++) {
            if (currentEnd <= ranges[idx][0]) {
                currentEnd = ranges[idx][1];
                nonOverlapCount++;
            }
        }
        return ranges.size() - nonOverlapCount;
    }
};

Partition Labels Tecnhique

This approach tracks last character occurrences to determine optimal partitions:

vector<int> labelPartitions(string s) {
    vector<int> lastPos(26, 0);
    vector<int> partitionSizes;
    
    for (int idx = 0; idx < s.length(); idx++) {
        lastPos[s[idx] - 'a'] = idx;
    }
    
    int segmentStart = 0, segmentEnd = 0;
    for (int idx = 0; idx < s.length(); idx++) {
        segmentEnd = max(segmentEnd, lastPos[s[idx] - 'a']);
        if (segmentEnd == idx) {
            partitionSizes.push_back(segmentEnd - segmentStart + 1);
            segmentStart = idx + 1;
        }
    }
    return partitionSizes;
}

Interval Merging Strategy

Merge overlapping intervals by updating boundaries during traversal:

class IntervalMerger {
public:
    static bool compareStarts(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    
    vector<vector<int>> combineIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), compareStarts);
        vector<vector<int>> merged;
        merged.push_back(intervals[0]);
        
        for (int idx = 1; idx < intervals.size(); idx++) {
            if (intervals[idx][0] <= merged.back()[1]) {
                merged.back()[1] = max(intervals[idx][1], merged.back()[1]);
            } else {
                merged.push_back(intervals[idx]);
            }
        }
        return merged;
    }
};