🚀 Day 4: Mastering the Merge Intervals Pattern (Amazon Interview Series)

The Merge Intervals Pattern is all about managing overlapping ranges.
Amazon loves this pattern because its business is filled with scheduling problems:

• Meeting room allocation (AWS teams, internal scheduling)
• Delivery time windows (Amazon Logistics)
• Calendar management (Amazon Chime, WorkDocs)
• Resource allocation (EC2 instance booking windows)

---

🔑 Core Idea

1. Sort intervals by start time.
2. Iterate through intervals, merging overlaps.
3. If current interval overlaps with previous → merge. Else → add new.

When Amazon uses this:

• Scheduling problems
• Range overlaps
• Time/resource allocation

---

📝 Problem 1: Merge Intervals

👉 Amazon-style phrasing:
Given an array of intervals, merge all overlapping intervals.

Java Solution

import java.util.*;

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();

        int[] current = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= current[1]) {
                current[1] = Math.max(current[1], intervals[i][1]); // merge
            } else {
                merged.add(current);
                current = intervals[i];
            }
        }
        merged.add(current);

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

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] result = merge(intervals);
        for (int[] arr : result) {
            System.out.println(Arrays.toString(arr));
        }
        // Output: [1,6], [8,10], [15,18]
    }
}

✅ Time Complexity: O(n log n) (sorting dominates).
✅ Why Amazon asks: Real-world scheduling & AWS resource allocation.

---

📝 Problem 2: Insert Interval

👉 Amazon-style phrasing:
You are given a list of non-overlapping intervals sorted by start time. Insert a new interval into the list and merge if necessary.

Java Solution

import java.util.*;

public class InsertInterval {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;

        // Add all before overlap
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i++]);
        }

        // Merge overlap
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Add rest
        while (i < intervals.length) {
            result.add(intervals[i++]);
        }

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

✅ Amazon focus: Insert + merge operations (very common).

---

📝 Problem 3: Minimum Meeting Rooms

👉 Amazon-style phrasing:
Given meeting time intervals, find the minimum number of conference rooms required.

Java Solution

import java.util.*;

public class MeetingRoomsII {
    public static int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;

        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);

        int rooms = 0, endPtr = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (start[i] < end[endPtr]) {
                rooms++; // new room needed
            } else {
                endPtr++; // reuse room
            }
        }
        return rooms;
    }

    public static void main(String[] args) {
        int[][] meetings = {{0,30},{5,10},{15,20}};
        System.out.println(minMeetingRooms(meetings)); // Output: 2
    }
}

✅ Amazon focus: Resource optimization — this maps directly to AWS resource scheduling.

---

📝 Problem 4: Employee Free Time

👉 Amazon-style phrasing:
Given employees’ working intervals, return the common free time intervals.

Java Solution

import java.util.*;

class Interval {
    int start, end;
    Interval(int s, int e) { start = s; end = e; }
}

public class EmployeeFreeTime {
    public static List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> all = new ArrayList<>();
        for (List<Interval> list : schedule) {
            all.addAll(list);
        }

        all.sort((a, b) -> a.start - b.start);
        List<Interval> result = new ArrayList<>();
        int end = all.get(0).end;

        for (int i = 1; i < all.size(); i++) {
            if (all.get(i).start > end) {
                result.add(new Interval(end, all.get(i).start));
            }
            end = Math.max(end, all.get(i).end);
        }
        return result;
    }
}

✅ Amazon focus: Think beyond “merge overlaps” → now find “gaps”.

---

📚 Extended Problem List (Practice)

1. Meeting Rooms I (LeetCode 252) – Just check if all meetings can be attended.
2. Interval List Intersections – Find intersections between two lists of intervals.
3. Maximum CPU Load – Given jobs with start/end/load, find max CPU load at any time.
4. Airplane Landing & Takeoff – Find the maximum planes in the sky at once.
5. Range Module – Add/remove/query intervals dynamically.

---

🎯 Key Takeaways

• Always sort by start time first.
• Merge = handle overlaps, Free Time = handle gaps.

• Amazon often disguises this as:

  • Calendar scheduling
  • CPU utilization
  • Logistics & delivery slots
  • AWS resource booking

---

📅 Next in the series (Day 5):
👉 Monotonic Stack & Queue Pattern – powerful for “Next Greater Element”, “Daily Temperatures”, and “Trapping Rain Water” (Amazon’s most loved stack interview set).