Remove Minimum Intervals to Eliminate Overlaps

Given a list of intervals, determine the minimum number of intervals to remove so that the remaining ones do not overlap. Adjacent intervals like [1,2] and [2,3] are not considered overlapping.

A greedy approach works by sorting intervals by their end points. After sorting, iterate through the list and count how many non-overlapping intervals can be selected. The answer is the total count minus this number.

class Solution {
public:
    static bool compare(const vector<int>& x, const vector<int>& y) {
        return x[1] < y[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& segments) {
        if (segments.empty()) return 0;
        sort(segments.begin(), segments.end(), compare);

        int kept = 1;
        int lastEnd = segments[0][1];

        for (int i = 1; i < segments.size(); ++i) {
            if (segments[i][0] >= lastEnd) {
                kept++;
                lastEnd = segments[i][1];
            }
        }
        return segments.size() - kept;
    }
};

Partition String into Maximum Letter-Segments

Partition a string into as many parts as possible so that each character appears in only one segment. Return the sizes of these segments.

The key insight is to record the last occurrence index of every chraacter. While scanning the string, maintain farthest position any character in the current segment reaches. When the current index matches this farthest position, a valid partition is found.

class Solution {
public:
    vector<int> partitionLabels(string str) {
        int lastPos[26] = {0};
        for (int i = 0; i < str.size(); ++i) {
            lastPos[str[i] - 'a'] = i;
        }

        vector<int> lengths;
        int start = 0, maxReach = 0;

        for (int i = 0; i < str.size(); ++i) {
            maxReach = max(maxReach, lastPos[str[i] - 'a']);
            if (i == maxReach) {
                lengths.push_back(i - start + 1);
                start = i + 1;
            }
        }
        return lengths;
    }
};

Meerge Overlapping Intervals

Given a collection of intervals, merge all overlapping ones.

Sort intervals by their start points. Then traverse the sorted list, merging an interval with the previous one if its start is less than or equal to the previous end. Update the end to the maximum of both ends during merging.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& ranges) {
        if (ranges.empty()) return {};
        sort(ranges.begin(), ranges.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        vector<vector<int>> merged;
        merged.push_back(ranges[0]);

        for (int i = 1; i < ranges.size(); ++i) {
            if (merged.back()[1] >= ranges[i][0]) {
                merged.back()[1] = max(merged.back()[1], ranges[i][1]);
            } else {
                merged.push_back(ranges[i]);
            }
        }
        return merged;
    }
};