Binary Search TreesProblem 18 of 22
Given n appointments, find the conflicting appointments
Problem Statement
Given n appointments, where each appointment has a start and end time, find all conflicting appointments. Two appointments conflict if they overlap (one starts before the other ends).
Example:
Appointments: [(1,5), (3,7), (2,6), (10,15), (5,6), (4,100)]
Conflicts:
- (1,5) conflicts with (3,7), (2,6), (4,100)
- (3,7) conflicts with (1,5), (2,6), (5,6), (4,100)
- (2,6) conflicts with (1,5), (3,7), (5,6), (4,100)
- (10,15) conflicts with (4,100)
- (5,6) conflicts with (3,7), (2,6), (4,100)
- (4,100) conflicts with all others
Approach 1: Brute Force (Check All Pairs)
Intuition
Compare every pair of appointments to check if they conflict.
Algorithm
- For each pair (i, j) where i < j
- Check if appointments overlap
- Two intervals [a, b] and [c, d] overlap if: a < d && c < b
java
import java.util.*;
class Appointment {
int start, end, index;
Appointment(int s, int e, int i) { start = s; end = e; index = i; }
}
public class Solution {
private boolean conflicts(Appointment a, Appointment b) {
return a.start < b.end && b.start < a.end;
}
public List<int[]> findConflictsBruteForce(List<Appointment> appointments) {
List<int[]> conflictPairs = new ArrayList<>();
int n = appointments.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (conflicts(appointments.get(i), appointments.get(j))) {
conflictPairs.add(new int[]{i, j});
}
}
}
return conflictPairs;
}
}Complexity Analysis
- Time Complexity: O(n^2) - Check all pairs
- Space Complexity: O(1) - Excluding output
Approach 2: Optimal (Using Interval Tree / BST)
Intuition
Use an interval tree or BST sorted by start time. For each new appointment, find all overlapping intervals efficiently.
Algorithm
- Sort appointments by start time
- Use BST/balanced tree to store appointments
- For each appointment, query tree for conflicts
- Insert appointment into tree
java
import java.util.*;
class Appointment {
int start, end, index;
Appointment(int s, int e, int i) { start = s; end = e; index = i; }
}
public class Solution {
public List<int[]> findConflictsOptimal(List<Appointment> appointments) {
List<int[]> conflicts = new ArrayList<>();
int n = appointments.size();
// Create sorted copy with original indices
List<Appointment> sorted = new ArrayList<>();
for (int i = 0; i < n; i++) {
sorted.add(new Appointment(
appointments.get(i).start,
appointments.get(i).end,
i
));
}
sorted.sort((a, b) -> {
if (a.start != b.start) return a.start - b.start;
return a.end - b.end;
});
// Active appointments sorted by end time
TreeMap<Integer, List<Integer>> active = new TreeMap<>();
for (Appointment appt : sorted) {
int start = appt.start;
int end = appt.end;
int idx = appt.index;
// Remove appointments that have ended
while (!active.isEmpty() && active.firstKey() <= start) {
active.pollFirstEntry();
}
// All remaining active appointments conflict with current
for (List<Integer> indices : active.values()) {
for (int conflictIdx : indices) {
conflicts.add(new int[]{
Math.min(idx, conflictIdx),
Math.max(idx, conflictIdx)
});
}
}
// Add current appointment
active.computeIfAbsent(end, k -> new ArrayList<>()).add(idx);
}
return conflicts;
}
}Complexity Analysis
- Time Complexity: O(n log n + k) where k is number of conflicts
- Space Complexity: O(n) - For sorting and active set
Approach 3: Line Sweep Algorithm
Intuition
Use line sweep - create events for start and end of each appointment. Process events in sorted order.
Algorithm
- Create start and end events for each appointment
- Sort events by time (start before end at same time)
- Maintain active set of appointments
- When starting, all active appointments conflict with new one
java
import java.util.*;
public class Solution {
public List<int[]> findConflictsSweep(int[][] appointments) {
List<int[]> events = new ArrayList<>();
int n = appointments.length;
for (int i = 0; i < n; i++) {
events.add(new int[]{appointments[i][0], 0, i}); // start
events.add(new int[]{appointments[i][1], 1, i}); // end
}
// Sort by time, then by type (start before end)
events.sort((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
Set<Integer> active = new HashSet<>();
List<int[]> conflicts = new ArrayList<>();
for (int[] event : events) {
int time = event[0];
int type = event[1];
int idx = event[2];
if (type == 0) { // Start
for (int activeIdx : active) {
conflicts.add(new int[]{
Math.min(idx, activeIdx),
Math.max(idx, activeIdx)
});
}
active.add(idx);
} else { // End
active.remove(idx);
}
}
return conflicts;
}
}Complexity Analysis
- Time Complexity: O(n log n + k) - Sorting + k conflict pairs
- Space Complexity: O(n)
Approach 4: Check If Any Conflict Exists (Simpler Problem)
Intuition
If we only need to know IF there are conflicts (not all of them), we can sort and check adjacent appointments.
java
import java.util.*;
public class Solution {
public boolean hasConflict(int[][] appointments) {
if (appointments.length == 0) return false;
// Sort by start time
Arrays.sort(appointments, (a, b) -> a[0] - b[0]);
// Check adjacent appointments
for (int i = 1; i < appointments.length; i++) {
if (appointments[i][0] < appointments[i-1][1]) {
return true;
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Sorting dominates
- Space Complexity: O(1) or O(n) depending on sorting
Key Takeaways
- Overlap condition: [a,b] overlaps [c,d] iff a < d && c < b
- Line sweep: Classic technique for interval problems
- Events approach: Treat start/end as separate events
- Active set: Track currently active intervals
- BST/Set: Useful for maintaining sorted active intervals
- This problem is related to interval scheduling and calendar conflicts
- Similar to: Meeting Rooms, Merge Intervals, Insert Interval