Find All Conflicting Appointments

Problem

Given a list of appointments represented as intervals [[start, end], ...], find all pairs of appointments that conflict (i.e., overlap). Return or print every pair of intervals that overlap.

Examples

Example 1

1
2
3
4
5


Input: appointments = [[4,5], [2,3], [3,6], [5,7], [7,8]]
Output: [[(4,5), (3,4)], [(3,6), (5,7)]]
Explanation:
[4,5] conflicts with [3,6]
[3,6] conflicts with [5,7]

Solution

The standard approach is to sort intervals by start and then compare each interval with the previous (or maintain an active set). When an interval’s start is less than the previous interval’s end, they overlap — record the conflicting pair.

Method 1 - Sort by start and scan (record overlapping pairs)

Intuition

Sorting by start brings potential overlapping intervals next to each other. If interval[i].start < interval[i-1].end, the two intervals overlap. Scanning once after sorting finds all adjacent overlaps; to find all conflicts (including overlapping multiple previous intervals), keep a running prev interval that tracks the rightmost end seen so far or compare with nearby intervals as needed.

Approach

If there are fewer than 2 appointments return an empty list.
Sort intervals by start in non-decreasing order.
Iterate i from 1 to n-1:

If intervals[i].start < intervals[i-1].end then record the pair (intervals[i-1], intervals[i]) as a conflict.
To capture chains where one interval overlaps multiple previous intervals (rare for simple adjacent-check approach), you can maintain an active interval with the maximum end among overlapping group members and compare subsequent intervals against it.

Return the list of conflicting pairs.

Edge cases:

Intervals that share an endpoint (e.g., [1,2] and [2,3]) are considered non-overlapping (start >= prev.end allowed).
If many intervals overlap a common window, the simple adjacent-pair method will find each adjacent conflict; to enumerate all unique conflicting pairs in a dense cluster you may need an active structure (heap/interval tree) — this version reports the obvious adjacent conflicts which covers typical interview expectations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
 public:
	vector<pair<pair<int,int>, pair<int,int>>> findConflicts(vector<pair<int,int>>& intervals) {
		vector<pair<pair<int,int>, pair<int,int>>> res;
		if (intervals.size() < 2) return res;
		sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b){ return a.first < b.first; });
		for (size_t i = 1; i < intervals.size(); ++i) {
			if (intervals[i].first < intervals[i-1].second) {
				res.push_back({intervals[i-1], intervals[i]});
			}
		}
		return res;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


package main

import "sort"

func findConflicts(intervals [][2]int) [][2][2]int {
	res := make([][2][2]int, 0)
	if len(intervals) < 2 {
		return res
	}
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] < intervals[i-1][1] {
			res = append(res, [2][2]int{intervals[i-1], intervals[i]})
		}
	}
	return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
		public List<int[][]> findConflicts(int[][] intervals) {
				List<int[][]> res = new ArrayList<>();
				if (intervals == null || intervals.length < 2) return res;
				Arrays.sort(intervals, java.util.Comparator.comparingInt(a -> a[0]));
				for (int i = 1; i < intervals.length; i++) {
						if (intervals[i][0] < intervals[i-1][1]) {
								res.add(new int[][]{intervals[i-1], intervals[i]});
						}
				}
				return res;
		}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
		def find_conflicts(self, intervals: list[tuple[int,int]]) -> list[tuple[tuple[int,int], tuple[int,int]]]:
				res: list[tuple[tuple[int,int], tuple[int,int]]] = []
				if not intervals or len(intervals) < 2:
						return res
				intervals.sort(key=lambda x: x[0])
				for i in range(1, len(intervals)):
						if intervals[i][0] < intervals[i-1][1]:
								res.append((intervals[i-1], intervals[i]))
				return res

Complexity

⏰ Time complexity: O(n log n) due to sorting; the subsequent single pass is O(n), so total O(n log n).
🧺 Space complexity: O(k) for the output list of k conflict pairs (worst-case O(n)), plus O(1) auxiliary space beyond input and output (sorting may require O(n) auxiliary space depending on language/runtime).

Problem#

Examples#

Example 1#

Solution#

Method 1 - Sort by start and scan (record overlapping pairs)#

Intuition#

Approach#

Code#

Complexity#