Optimizing Disjoint Interval Selection

Problem Statement: Given a collection of time ranges represented as pairs \[start, end\], determine the minimum number of ranges that must be discarded to ensure the remaining set contains no overlaps.

Approach: This scenario is best resolved using a greedy strategy. By arranging the intervals according to their starting points, we can iterate through them sequentially. We maintain a reference to the end point of the last non-conflicting interval selected. Whenever a new interval begins before this reference point, an overlap exists. At this juncture, we increment a removal counter. Crucially, to maximize future compatibility, when an overlap is detected, we adjust our reference end point to the smaller of the two conflicting endpoints. This effectively keeps the tighter interval and discards the looser one.

public class IntervalOptimizer {
    public static int calculateMinDeletions(int[][] rangeSet) {
        // Sort ranges based on the starting coordinate
        Arrays.sort(rangeSet, (a, b) -> Integer.compare(a[0], b[0]));

        int removedCount = 0;
        // Initialize with the end of the first interval
        int prevEnd = rangeSet[0][1];

        for (int idx = 1; idx < rangeSet.length; idx++) {
            int[] current = rangeSet[idx];
            
            // Check for intersection
            if (current[0] < prevEnd) {
                removedCount++;
                // Retain the interval that ends sooner to minimize blocking future ones
                prevEnd = Math.min(prevEnd, current[1]);
            } else {
                // No overlap, move the reference to the current end
                prevEnd = current[1];
            }
        }

        return removedCount;
    }
}

Partitioning Strings by Character Boundaries

Problem Statement: You are provided with a text string inputText. The goal is to split this string into the maximum number of parts such that no character appears in more than one part. Return the length of each resulting partition.

Approach: To solve this efficiently, we first scan the entire input to record the final appearance index for every unique character present. During a second traversal, we track the farthest position required to complete the current segment. As we iterate, we update the segment's boundary based on the latest occurrence of the current character. Once the iterasion index reaches this calculated boundary, we know all characters within that window have been accounted for, allowing us to finalize the segment and begin a new one.

public class TextSegmenter {
    public static List<Integer> getPartitionSizes(String inputText) {
        int[] lastIndexMap = new int[26];
        
        // Identify the last index for each character
        for (int i = 0; i < inputText.length(); i++) {
            lastIndexMap[inputText.charAt(i) - 'a'] = i;
        }

        List<Integer> partitionResults = new ArrayList<>();
        int segmentStart = 0;
        int segmentBoundary = 0;

        for (int i = 0; i < inputText.length(); i++) {
            // Expand the current segment boundary if needed
            segmentBoundary = Math.max(segmentBoundary, lastIndexMap[inputText.charAt(i) - 'a']);

            // If the current index matches the boundary, close the segment
            if (i == segmentBoundary) {
                partitionResults.add(i - segmentStart + 1);
                segmentStart = i + 1;
            }
        }
        return partitionResults;
    }
}

Merging Overlapping Time Ranges

Problem Statement: Accept a list of intervals where overlapping regions exist. Combine these intersecting ranges into a single contiguous span and produce a clean list containing only non-overlapping merged intervals that cover the original data completely.

Approach: Similar to finding overlaps, the key here is to sort the dataset by the initial coordinate. We then initialize a collection with the first sorted interval. For each subsequent interval, we compare its start point against the end point of the last item added to our result list. If the new start is less than or equal to the existing end, an overlap is confirmed. In this case, we merge them by updating the end of the last recorded interval to the maximum of both ends. If there is no overlap, the current interval is added as a distinct entry.

public class RangeMerger {
    public static int[][] unifyRanges(int[][] rawIntervals) {
        if (rawIntervals.length == 0) {
            return new int[0][];
        }

        // Order intervals by start time
        Arrays.sort(rawIntervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> mergedList = new ArrayList<>();
        
        for (int[] interval : rawIntervals) {
            // If list is empty or no overlap with previous interval
            if (mergedList.isEmpty() || mergedList.get(mergedList.size() - 1)[1] < interval[0]) {
                mergedList.add(interval);
            } else {
                // Overlap detected: merge by extending the end boundary
                int[] last = mergedList.get(mergedList.size() - 1);
                last[1] = Math.max(last[1], interval[1]);
            }
        }

        return mergedList.toArray(new int[mergedList.size()][]);
    }
}