Interval Problems (Merge, Insert, Meeting Rooms)

Merge Intervals (LeetCode 56)

Sort the intervals by their start time, then check if the current interval overlaps with the last added interval.

int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // Sort by start point
    List<int[]> res = new ArrayList<>();

    for (int[] cur : intervals) {
        if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) {
            res.add(cur);  // No overlap, add directly
        } else {
            // Overlap, update the end point of the last interval
            res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], cur[1]);
        }
    }
    return res.toArray(new int[res.size()][]);
}

Insert Interval (LeetCode 57)

In an already sorted and non-overlapping interval list, insert a new interval and merge if necessary. This can be handled in three phases:

int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;

    // 1. All intervals that end before the new interval starts (no overlap)
    while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);

    // 2. All intervals that overlap with the new interval (merge them)
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.add(newInterval);

    // 3. All intervals that start after the new interval ends (no overlap)
    while (i < n) res.add(intervals[i++]);

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

Meeting Rooms I (LeetCode 252)

Determine if a person could attend all meetings (i.e., NO overlapping intervals):

boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) return false;
    }
    return true;
}

Meeting Rooms II (LeetCode 253)

Find the minimum number of conference rooms required (equivalent to the maximum number of concurrent meetings):

Min-Heap Greedy Approach: Sort meetings by start time. Use a Min-Heap to store the end times of ongoing meetings. If the meeting ending the earliest lets out before the current meeting starts, reuse that room. Otherwise, open a new room.

int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> endTimes = new PriorityQueue<>();  // Tracks earliest end times

    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll();  // Reuse room: remove the old end time
        }
        endTimes.offer(interval[1]); // Add new end time (either new or reused room)
    }
    return endTimes.size();
}

Alternative Difference Array / Line Sweep logic: Sort start points and end points separately to track active room count over time.

Partition Labels (LeetCode 763)

Greedy: Partition a string into as many parts as possible such that each letter appears in at most one part.

List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    // Pre-record the last index of each character
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;

    List<Integer> res = new ArrayList<>();
    int start = 0, currentEnd = 0;
    for (int i = 0; i < s.length(); i++) {
        // Expand the boundary to include the last occurrence of the current character
        currentEnd = Math.max(currentEnd, last[s.charAt(i) - 'a']);
        if (i == currentEnd) {
            res.add(currentEnd - start + 1);
            start = currentEnd + 1;
        }
    }
    return res;
}