Sorting Problems Tutorial: Merge Intervals & Greedy Algorithms for Interviews

The Problem That Made Sorting Click

An interviewer asked: "Given a list of meeting time intervals, determine if a person can attend all meetings." I saw overlapping intervals needed checking, but my solution was messy and O(n²).

Then they said: "What if you sort first?" Suddenly, the problem became trivial—after sorting, just check if any meeting starts before the previous one ends!

That's when I realized: sorting often isn't the problem—it's the solution technique. Many hard problems become easy after sorting.

In this guide, I'll share the sorting-based patterns that transformed complex problems into simple solutions. You'll learn when sorting is the right first step.

Pattern 1: Interval Problems

Merge Intervals

LeetCode #56 - Merge Intervals

def merge_intervals(intervals):
    """
    Merge overlapping intervals.
    Sort by start time, then merge.
    """
    if not intervals:
        return []

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

    merged = [intervals[0]]

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

        # Check if overlaps with last merged interval
        if current[0] <= last[1]:
            # Merge: extend end time
            last[1] = max(last[1], current[1])
        else:
            # No overlap: add as new interval
            merged.append(current)

    return merged

Time: O(n log n) for sort + O(n) for merge = O(n log n)

Test: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

Key insight: After sorting, overlapping intervals are adjacent!

Meeting Rooms

LeetCode #252 - Meeting Rooms

def can_attend_meetings(intervals):
    """
    Check if person can attend all meetings (no overlaps).
    Sort and check adjacent intervals.
    """
    if not intervals:
        return True

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

    # Check each pair of adjacent meetings
    for i in range(len(intervals) - 1):
        if intervals[i][1] > intervals[i+1][0]:
            return False  # Overlap found

    return True

Pattern: Sort + check adjacent pairs

Meeting Rooms II (Minimum Rooms)

LeetCode #253 - Meeting Rooms II

def min_meeting_rooms(intervals):
    """
    Find minimum rooms needed for all meetings.
    Sort start and end times separately.
    """
    if not intervals:
        return 0

    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])

    rooms = 0
    max_rooms = 0
    start_ptr = end_ptr = 0

    while start_ptr < len(intervals):
        if starts[start_ptr] < ends[end_ptr]:
            # Meeting starts before earliest ends
            rooms += 1
            max_rooms = max(max_rooms, rooms)
            start_ptr += 1
        else:
            # A room becomes free
            rooms -= 1
            end_ptr += 1

    return max_rooms

Clever insight: Track when meetings start and end separately. When a meeting starts before earliest end, need an extra room!

Pattern 2: Sorting + Two Pointers

3Sum Closest

LeetCode #16 - 3Sum Closest

def three_sum_closest(nums, target):
    """
    Find three numbers closest to target.
    Sort + two pointers for each element.
    """
    nums.sort()
    closest_sum = float('inf')

    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            # Update closest
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            # Move pointers
            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return current_sum  # Exact match!

    return closest_sum

Pattern: Sort enables two-pointer technique

Squares of Sorted Array

LeetCode #977 - Squares of a Sorted Array

def sorted_squares(nums):
    """
    Square elements and return sorted (without re-sorting).
    Two pointers from both ends.
    """
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1

    # Fill from right to left (largest to smallest)
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) > abs(nums[right]):
            result[i] = nums[left] ** 2
            left += 1
        else:
            result[i] = nums[right] ** 2
            right -= 1

    return result

Clever trick: Array is already sorted. Largest absolute values are at ends!

Pattern 3: Custom Sorting

Largest Number

LeetCode #179 - Largest Number

from functools import cmp_to_key

def largest_number(nums):
    """
    Arrange numbers to form largest number.
    Custom comparator: compare concatenations.
    """
    # Convert to strings
    nums = list(map(str, nums))

    # Custom comparator
    def compare(x, y):
        # Compare xy vs yx
        if x + y > y + x:
            return -1  # x should come first
        elif x + y < y + x:
            return 1   # y should come first
        else:
            return 0

    # Sort with custom comparator
    nums.sort(key=cmp_to_key(compare))

    # Handle edge case: all zeros
    if nums[0] == '0':
        return '0'

    return ''.join(nums)

Test: [3, 30, 34, 5, 9] → "9534330"

Insight: Compare x+y vs y+x to determine order!

Sort Characters By Frequency

LeetCode #451 - Sort Characters By Frequency

from collections import Counter

def frequency_sort(s):
    """
    Sort characters by frequency (descending).
    Count, then sort by count.
    """
    # Count frequencies
    count = Counter(s)

    # Sort by frequency (descending), then alphabetically
    sorted_chars = sorted(count.items(), key=lambda x: (-x[1], x[0]))

    # Build result
    return ''.join(char * freq for char, freq in sorted_chars)

Alternative: Use bucket sort for O(n):

def frequency_sort_bucket(s):
    """Bucket sort by frequency."""
    count = Counter(s)

    # Buckets: index = frequency
    buckets = [[] for _ in range(len(s) + 1)]
    for char, freq in count.items():
        buckets[freq].append(char)

    # Build result from highest frequency
    result = []
    for freq in range(len(s), 0, -1):
        for char in buckets[freq]:
            result.append(char * freq)

    return ''.join(result)

Pattern 4: Sorting for Greedy Algorithms

Non-overlapping Intervals

LeetCode #435 - Non-overlapping Intervals

def erase_overlap_intervals(intervals):
    """
    Minimum removals to make non-overlapping.
    Sort by end time, greedily keep earliest ending.
    """
    if not intervals:
        return 0

    # Sort by end time
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < end:
            # Overlaps: remove current
            count += 1
        else:
            # No overlap: update end
            end = intervals[i][1]

    return count

Greedy insight: Always keep interval that ends earliest (leaves most room for others)!

Minimum Arrows to Burst Balloons

LeetCode #452 - Minimum Number of Arrows to Burst Balloons

def find_min_arrows(points):
    """
    Minimum arrows to burst all balloons.
    Similar to non-overlapping intervals.
    """
    if not points:
        return 0

    # Sort by end position
    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:
            # Need new arrow
            arrows += 1
            arrow_pos = end

    return arrows

Pattern 5: Relative Ordering

Sort Array by Parity

LeetCode #905 - Sort Array by Parity

def sort_array_by_parity(nums):
    """
    Even numbers before odd (stable).
    Two pointers: one for even position, one for scanning.
    """
    even_pos = 0

    for i in range(len(nums)):
        if nums[i] % 2 == 0:
            nums[even_pos], nums[i] = nums[i], nums[even_pos]
            even_pos += 1

    return nums

Alternative: Custom sort key:

def sort_array_by_parity_v2(nums):
    return sorted(nums, key=lambda x: x % 2)

Relative Sort Array

LeetCode #1122 - Relative Sort Array

def relative_sort_array(arr1, arr2):
    """
    Sort arr1 so elements in arr2 come first (in arr2 order).
    Elements not in arr2 come after (sorted).
    """
    # Create order map
    order = {num: i for i, num in enumerate(arr2)}

    # Sort with custom key
    # Elements in arr2 get their index
    # Elements not in arr2 get large value + their value
    return sorted(arr1, key=lambda x: (order.get(x, 1000), x))

Pattern 6: Finding Kth Element After Sorting

Kth Largest Element (QuickSelect)

LeetCode #215 - Kth Largest Element

import random

def find_kth_largest(nums, k):
    """
    Find kth largest without full sort.
    QuickSelect: O(n) average.
    """
    def partition(left, right):
        # Random pivot to avoid worst case
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        pivot = nums[right]
        i = left

        for j in range(left, right):
            if nums[j] >= pivot:  # >= for descending
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        nums[i], nums[right] = nums[right], nums[i]
        return i

    left, right = 0, len(nums) - 1
    k_idx = k - 1  # kth largest is at index k-1 when sorted descending

    while True:
        pivot_idx = partition(left, right)

        if pivot_idx == k_idx:
            return nums[pivot_idx]
        elif pivot_idx < k_idx:
            left = pivot_idx + 1
        else:
            right = pivot_idx - 1

Time: O(n) average, O(n²) worst case

When to Sort vs When Not to Sort

Sort when:

• Need relative ordering
• Checking adjacent elements is useful
• Two pointers after sorting
• Greedy algorithms that depend on order

Don't sort when:

• Need original indices
• O(n) solution exists without sorting
• Sorting breaks problem structure
• Additional constraints make sorting useless

Example where sorting helps:

• Merge intervals, meeting rooms
• Two sum on sorted array
• Finding duplicates

Example where sorting doesn't help:

• Two sum on unsorted (hash map is O(n) vs O(n log n))
• Sliding window with fixed size
• Problems requiring original order

Sorting Stability in Practice

Stable sorts preserve relative order of equal elements:

# Stable: MergeSort, TimSort (Python default)
records = [('A', 2), ('B', 1), ('C', 2)]
sorted(records, key=lambda x: x[1])
# Result: [('B', 1), ('A', 2), ('C', 2)]
# A comes before C (both have value 2)

# Unstable: QuickSort, HeapSort might give:
# [('B', 1), ('C', 2), ('A', 2)]

When stability matters: Multi-level sorting, maintaining original order

My Practice Strategy

Week 1: Interval Problems

• Merge intervals variations
• Meeting rooms patterns
• 15-20 problems

Week 2: Sorting + Two Pointers

• 3Sum, 4Sum family
• Sorted array manipulations
• 15-20 problems

Week 3: Custom Sorting

• Custom comparators
• Relative ordering
• 10-15 problems

Week 4: Mixed Problems

• 30+ problems where sorting is a step
• Practice recognizing when to sort
• Optimize: when is sorting worth it?

Real Interview Success

I was asked: "Given arrival and departure times, find minimum platforms needed."

My approach:

1. "This is like meeting rooms" → Sort start and end separately
2. Track concurrent trains
3. Similar to meeting rooms II pattern

Coded in 12 minutes using the sorting pattern!

Conclusion: Your Sorting Problems Mastery

Sorting problems aren't about sorting algorithms—they're about recognizing when sorting simplifies the problem:

1. Intervals - Sort by start time or end time
2. Two pointers - Sort enables efficient O(n) solutions
3. Custom sorting - Define your own specific order
4. Greedy - Sort to enable optimal greedy choices
5. Kth element - Use QuickSelect without needing full sort

Master these patterns, and you'll see sorting opportunities everywhere.

Within 3-4 weeks of consistent practice, you'll instantly recognize: "If I sort first, this becomes easy!" You'll also develop intuition for when sorting overhead is worth the simplified logic. Remember: the goal isn't to memorize solutions—it's to recognize patterns so you can adapt them to new problems you've never seen before. Start practicing today!

Remember: sorting transforms chaos into order—use that powerful transformation to your advantage in every interview!

Happy coding, and may your problems always be elegantly sortable!