Welcome to Day 5 of your coding interview journey.

So far, you’ve learned:

• ✅ Day 1: HashMaps
• ✅ Day 2: Sliding Window
• ✅ Day 3: Arrays
• ✅ Day 4: Two Pointers

Today’s focus is a very common interview pattern:

👉 Interval Problems

These questions test your ability to handle ranges, overlaps, and sorting logic.

---

🧠 What Are Interval Problems?

You are given a list of intervals:

[start, end]

And asked to:

• Merge them
• Find overlaps
• Insert new intervals
• Determine conflicts

---

🔑 When Should You Use This Pattern?

Look for:

• Ranges of time (meetings, schedules)
• Overlapping segments
• Start and end values
• Questions involving merging or conflicts

---

💡 Problem – Merge Intervals

---

🧩 Problem

Given an array of intervals where intervals[i] = [start, end]:

👉 Merge all overlapping intervals and return the result.

---

✅ Example

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

---

❌ Brute Force Idea

• Compare every interval with every other
  👉 Time Complexity: O(n²)

Too slow for interviews.

---

✅ Optimal Approach – Sort + Merge

---

🧠 Key Idea

1. Sort intervals by start time
2. Compare current interval with the last merged one
3. Merge if overlapping, otherwise add new interval

---

🛠️ Solution in Python

def merge_intervals(intervals):
    # Step 1: Sort by start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for current in intervals[1:]:
        last = merged[-1]

        # Check overlap
        if current[0] <= last[1]:
            # Merge intervals
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)

    return merged

---

🎯 Step-by-Step Intuition

Input:

[1,3], [2,6]

• Since 2 <= 3 → overlap
• Merge → [1,6]

---

⚡ Complexity Analysis

• Time: O(n log n) (sorting)
• Space: O(n) (result)

---

🔥 Key Pattern

👉 Sort first, then process linearly

This pattern appears in MANY problems.

---

⚠️ Common Mistakes

• ❌ Forgetting to sort intervals
• ❌ Incorrect overlap condition
• ❌ Not updating the merged interval correctly
• ❌ Edge cases (single interval, empty input)

---

🧪 Practice Problems

To master intervals, try:

1. Insert Interval
2. Non-overlapping intervals
3. Meeting rooms I & II
4. Minimum number of arrows to burst balloons
5. Employee free time

---

🎯 Key Takeaways

• Interval problems almost always start with sorting
• Focus on:
  • Overlap detection
  • Merging logic
• Reduce complexity by avoiding nested loops

---

🚀 Your Challenge (Day 5)

Solve this:

Given a list of meeting intervals, determine if a person can attend all meetings.

(Hint: check for overlaps after sorting 😉)

---

📌 Final Thoughts

Interval problems are extremely common in real-world scenarios:

• Scheduling systems
• Calendar apps
• Resource allocation

Mastering them gives you a huge advantage in interviews.