Challenge: Appointment Scheduling Conflicts

Scenario:
A small business offers appointment-based services, and they want a system to detect scheduling conflicts. You are tasked with writing a program to determine if any of the scheduled appointments overlap.

Requirements:

Input:
- An array of appointments, where each appointment has:
  - id (number): A unique identifier for the appointment.
  - startTime (string): The start time in ISO 8601 format (e.g., "2024-12-07T10:00:00").
  - endTime (string): The end time in ISO 8601 format (e.g., "2024-12-07T11:30:00").
Output:
- An array of conflicts, where each conflict is represented as:
  
  typescript
  
  Copy code
  
  { appointment1: number, appointment2: number }
  
  appointment1 and appointment2 are the ids of conflicting appointments.
Behavior:
- Two appointments conflict if their time intervals overlap (i.e., one starts before the other ends).
- Assume all times are in the same time zone and formatted correctly.
- Handle edge cases like an empty input array or appointments with invalid times.
Stretch Features:
- Add a clientName field to the appointments and group conflicts by client.
- Suggest rescheduling options to resolve conflicts.

Example Input:

typescript

Copy code

const appointments = [ { id: 1, startTime: "2024-12-07T09:00:00", endTime: "2024-12-07T10:00:00" }, { id: 2, startTime: "2024-12-07T09:30:00", endTime: "2024-12-07T10:30:00" }, { id: 3, startTime: "2024-12-07T11:00:00", endTime: "2024-12-07T12:00:00" }, { id: 4, startTime: "2024-12-07T10:15:00", endTime: "2024-12-07T11:15:00" }, ];

Example Output:

typescript

Copy code

[ { appointment1: 1, appointment2: 2 }, { appointment1: 2, appointment2: 4 }, ]

Explanation:

Appointment 1 overlaps with Appointment 2.
Appointment 2 overlaps with Appointment 4.
Appointment 3 does not overlap with any others.

Tips:

Convert startTime and endTime to Date objects for comparison.
Use nested loops or sorting to identify overlaps efficiently:
- Option 1 (Simple): Compare every pair of appointments (O(n²)).
- Option 2 (Optimized): Sort by startTime and check consecutive appointments (O(n log n)).
Add checks for invalid or missing fields in the input.

Execution:

I gave myself 30 minutes and was able to get this right on time, although I’ll admit, my first execution did involve a weird Frankenstein’s monster of BOTH a double for loop AND sliding window pointers to do the operations redundantly. Wildly, it still worked, since the pointers actually weren’t used except for the let left = 0 during the initialization of the outer for loop.

The code below is what I did after I cleaned it up and got rid of the O(n^2) approach and into O(n) territory.

/*
 
 
input:
- array of appts.
  start and end, ISO 8601 format strings
 
output:
- array of conflists, where each conflict is represented as the ids of the conflicting appointments
  - return an array with 2 (or more?) ids
 
Functionality detail questions to get back to
- should we detect more than 2-way conflicts?
  ->> hypothetically conflicts could have chained overlaps
  ->> OR we could just detect ever possible set of 2 conflicting conflicts
    - keep running it as you resolve conflicts
 
 
O(n^2) naive approach is to
- consider every 2 item permutation in any order
- if there is a conflict, add it to conflicts (later return is)
- optionally dedupe conflicts by using a list of sets, or to dedupe them ad hoc some other way
 
improvement on naive approach
- we run the conflict detection function on a list that's is being popped off
 
order all items by startTime
order all items separately by endTime
for each item, left =0, right =last index
you move left over 1
 
*/
 
interface Appointment {
  id: number
  startTime: string
  endTime: string
}
 
interface Conflict {
  appointment1: number,
  appointment2: number
}
 
const appointments: Appointment[] = [
  { id: 1, startTime: "2024-12-07T09:00:00", endTime: "2024-12-07T10:00:00" },
  { id: 2, startTime: "2024-12-07T09:30:00", endTime: "2024-12-07T10:30:00" },
  { id: 3, startTime: "2024-12-07T11:00:00", endTime: "2024-12-07T12:00:00" },
  { id: 4, startTime: "2024-12-07T10:15:00", endTime: "2024-12-07T11:15:00" },
];
 
function detectConflicts(apps: Appointment[]): Conflict[] {
  const appsWithDates = apps.map(a=>{
    return {
      id: a.id,
      startTime: new Date(a.startTime),
      endTime: new Date(a.endTime)
    }
  })
  const appointmentsToScan = appsWithDates.sort((a, b)=>a.startTime.getTime()-b.startTime.getTime())
  const conflicts: Conflict[] = []
 
  let left = 0
  let right = 1
  while (left < appointmentsToScan.length-1){
    const app1 = appointmentsToScan[left]
    const app2 = appointmentsToScan[right]
 
    if (app1.endTime.getTime() < app2.startTime.getTime()){
      right++
      continue
    }
 
    conflicts.push({
      appointment1: app1.id,
      appointment2: app2.id
    })
 
    left++
    right=left+1
 
 
  }
 
  // example return statement
  return conflicts
}
 
console.log(detectConflicts(appointments))

I also thought of an approach that, now that I think of it I don’t know if it’s a performance boost - but it’s certainly more complex lol. Maybe this is a good moment to appreciate that, contrary to popular belief, more complex approaches don’t also provide increased performance.

I’m still trying to work it out out - the idea is to have 3 pointers iterating through two sorted lists.

Let me explain:


setup
1. add all apps to a hashmap for id based lookups
2. created a list of ids organized by ascending startTimes
4. one pointer is for the current appointment, so maybe currApp
5. the second pointer is for the earliest start time, so left
6. the third pointer is for the lastest endtime, so right

execution
1. set currApp to apps[0]
2. set left to apps[currApp+1]
3. set right to appse[currApp+2]
4. check if currApp.endTime < left.startTime
	1. if no, currApp and left are conflicts, add their ids
	2. then increment left and right
5. if not,

Hmm not sure if this is necessary. I guess the idea is that you could end execution early if the current app’s endTime is less than the next available startTime,

buuut I dunno if endTime really matters, since you only need to make the comparison in one direction and then you’re good.

Or well…there is a potential bug here still, where if you’re only comparing a < b one way, then…I dunno, I’m still not sure it’s airtight yet.

Appointment Conflicts