Sorting Problems Tutorial: Merge Intervals & Greedy Algorithms for Interviews
Master sorting-based problem solving with interval problems, meeting rooms, and greedy algorithms. Learn when sorting simplifies complex problems with Python. Includes merge intervals and QuickSelect
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:
- "This is like meeting rooms" â Sort start and end separately
- Track concurrent trains
- 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:
- Intervals - Sort by start time or end time
- Two pointers - Sort enables efficient O(n) solutions
- Custom sorting - Define your own specific order
- Greedy - Sort to enable optimal greedy choices
- 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!
If you found this guide helpful, share it with others learning algorithms. Recognizing when to sort is a crucial interview skill. If this guide helped you understand sorting applications or solve merge interval problems, I'd love to hear about it! Connect with me on Twitter or LinkedIn.
Support My Work
If this guide helped you master sorting-based problem solving, recognize interval patterns, or ace sorting interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.
â Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!
Cover image by UX Indonesia on Unsplash