Date range overlap detection in SQL - Time & Space Complexity

Time Complexity: Date range overlap detection

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find overlapping date ranges changes as the number of date ranges grows.

How does checking each pair for overlap scale when we have more date ranges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.id
FROM bookings a
JOIN bookings b ON a.id < b.id
  AND a.start_date <= b.end_date
  AND a.end_date >= b.start_date;
    

This query finds all pairs of bookings where the date ranges overlap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing each booking with every other booking to check for overlap.
• How many times: For n bookings, roughly n x (n - 1) / 2 comparisons happen.

How Execution Grows With Input

As the number of bookings grows, the number of comparisons grows much faster.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: Doubling the number of bookings roughly quadruples the comparisons.

Final Time Complexity

Time Complexity: O(n²)

This means the time to find overlaps grows quickly as the number of bookings increases, because each booking is checked against many others.

Common Mistake

[X] Wrong: "Checking overlaps only takes time proportional to the number of bookings (O(n))."

[OK] Correct: Because each booking must be compared with many others, the total checks grow much faster than just the number of bookings.

Interview Connect

Understanding how pairwise comparisons grow helps you explain performance in real systems that handle scheduling or reservations.

Self-Check

"What if we added an index on start_date and end_date? How would that affect the time complexity?"

Practice

1. What does date range overlap detection in SQL help you find?
SELECT * FROM bookings WHERE start_date <= '2024-05-10' AND end_date >= '2024-05-05';

easy

A. If dates are in the future only

B. If two date ranges share any common days

C. If dates are stored as strings

D. If one date range is completely before another

Solution

1. Step 1: Understand the condition

   The query checks if the booking's start date is on or before May 10 and the end date is on or after May 5.

2. Step 2: Interpret the overlap logic

   This means the booking period overlaps with the date range May 5 to May 10.

3. Final Answer:

   If two date ranges share any common days -> Option B

4. Quick Check:

   Date overlap means shared days = D [OK]

Hint: Check if start <= other end and end >= other start [OK]

Common Mistakes:

• Thinking overlap means one range is inside another
• Confusing date comparison operators
• Ignoring equal dates as overlap

2. Which SQL WHERE clause correctly detects overlap between two date ranges (start1, end1) and (start2, end2)?

easy

A. WHERE start1 < end2 AND end1 > start2

B. WHERE start1 > end2 OR end1 < start2

C. WHERE start1 = end2 AND end1 = start2

D. WHERE start1 <= end2 AND end1 >= start2

Solution

1. Step 1: Recall overlap condition

   Two ranges overlap if the start of one is on or before the end of the other, and the end of one is on or after the start of the other.

2. Step 2: Match condition to options

   WHERE start1 <= end2 AND end1 >= start2 uses <= and >= which correctly includes touching dates as overlap.

3. Final Answer:

   WHERE start1 <= end2 AND end1 >= start2 -> Option D

4. Quick Check:

   Overlap needs <= and >=, not just < or > [OK]

Hint: Use <= and >= to include touching dates as overlap [OK]

Common Mistakes:

• Using < and > excludes touching dates
• Using OR instead of AND
• Checking equality only

3. Given the table events(event_id, start_date, end_date) with data:
1, '2024-05-01', '2024-05-05'
2, '2024-05-04', '2024-05-10'
3, '2024-05-11', '2024-05-15'
What rows will this query return?
SELECT * FROM events WHERE start_date <= '2024-05-06' AND end_date >= '2024-05-04';

medium

A. Rows with event_id 1 and 2

B. Rows with event_id 2 and 3

C. Only row with event_id 2

D. All rows

Solution

1. Step 1: Check each event against the condition

   Condition: start_date <= '2024-05-06' AND end_date >= '2024-05-04'.
   Event 1: start '2024-05-01' <= '2024-05-06' (true), end '2024-05-05' >= '2024-05-04' (true) -> included.
   Event 2: start '2024-05-04' <= '2024-05-06' (true), end '2024-05-10' >= '2024-05-04' (true) -> included.
   Event 3: start '2024-05-11' <= '2024-05-06' (false) -> excluded.

2. Step 2: Determine final result set

   Only events 1 and 2 satisfy the overlap condition.

3. Final Answer:

   Rows with event_id 1 and 2 -> Option A

4. Quick Check:

   Events overlapping May 4-6 are 1 and 2 [OK]

Hint: Test each row's start and end against the range [OK]

Common Mistakes:

• Including event 3 which starts after the range
• Ignoring the >= condition on end_date
• Assuming only exact matches count

4. Identify the error in this SQL query intended to find overlapping bookings:
SELECT * FROM bookings WHERE start_date > '2024-05-01' AND end_date < '2024-05-10';

medium

A. All of the above

B. It uses > and < instead of >= and <=, missing overlaps

C. It only finds bookings fully inside the range, not overlapping ones

D. It excludes bookings that start or end exactly on the boundary dates

Solution

1. Step 1: Analyze the condition logic

   The query uses start_date > '2024-05-01' and end_date < '2024-05-10', which means it only selects bookings fully inside the range, excluding those starting or ending exactly on the boundaries.

2. Step 2: Understand overlap detection requirements

   Overlap detection requires using <= and >= to include touching dates and also to detect partial overlaps, not just fully contained bookings.

3. Step 3: Combine observations

   All options B, C, and D are true, so the query is incorrect for overlap detection.

4. Final Answer:

   All of the above -> Option A

5. Quick Check:

   All B, C, D are errors = A [OK]

Hint: Use inclusive operators and allow partial overlaps [OK]

Common Mistakes:

• Using strict > and < excludes boundary overlaps
• Assuming fully inside means overlap
• Not testing edge cases

5. You have a table reservations(id, start_date, end_date). Write a query to find all reservations that overlap with a new booking from '2024-06-10' to '2024-06-15'. Which query correctly detects overlaps including edge cases?

hard

A. SELECT * FROM reservations WHERE start_date < '2024-06-15' AND end_date > '2024-06-10';

B. SELECT * FROM reservations WHERE start_date BETWEEN '2024-06-10' AND '2024-06-15';

C. SELECT * FROM reservations WHERE start_date <= '2024-06-15' AND end_date >= '2024-06-10';

D. SELECT * FROM reservations WHERE end_date BETWEEN '2024-06-10' AND '2024-06-15';

Solution

1. Step 1: Understand overlap with inclusive edges

   Overlap means any shared day, including when one reservation ends exactly when the new booking starts or vice versa.

2. Step 2: Evaluate each option

   SELECT * FROM reservations WHERE start_date < '2024-06-15' AND end_date > '2024-06-10'; uses < and > which excludes exact boundary matches.
   SELECT * FROM reservations WHERE start_date <= '2024-06-15' AND end_date >= '2024-06-10'; uses <= and >= which includes edge overlaps.
   Options C and D only check if start or end is inside the new booking range, missing some overlaps.

3. Step 3: Choose the correct query

   SELECT * FROM reservations WHERE start_date <= '2024-06-15' AND end_date >= '2024-06-10'; correctly detects all overlaps including edge cases.

4. Final Answer:

   SELECT * FROM reservations WHERE start_date <= '2024-06-15' AND end_date >= '2024-06-10'; -> Option C

5. Quick Check:

   Inclusive operators catch all overlaps = B [OK]

Hint: Use <= and >= to catch all overlaps including edges [OK]

Common Mistakes:

• Using < and > excludes edge overlaps
• Using BETWEEN misses partial overlaps
• Checking only start or end date