101 Logo
onenoughtone

Code Implementation

Schedule Validator Implementation

Below is the implementation of the schedule validator:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Brute Force Approach
 * Time Complexity: O(n²) - We need to compare each meeting with every other meeting
 * Space Complexity: O(1) - We only use a constant amount of extra space
 * 
 * @param {number[][]} intervals - Array of meeting intervals [start, end]
 * @return {boolean} - True if all meetings can be attended, false otherwise
 */
function canAttendMeetingsBruteForce(intervals) {
  const n = intervals.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // Check if intervals[i] and intervals[j] overlap
      if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
        return false;
      }
    }
  }
  
  return true;
}
 
/**
 * Sorting Approach
 * Time Complexity: O(n log n) - Dominated by the sorting step
 * Space Complexity: O(1) - We only use a constant amount of extra space (assuming in-place sort)
 * 
 * @param {number[][]} intervals - Array of meeting intervals [start, end]
 * @return {boolean} - True if all meetings can be attended, false otherwise
 */
function canAttendMeetings(intervals) {
  // Sort intervals by start time
  intervals.sort((a, b) => a[0] - b[0]);
  
  // Check for overlaps between adjacent intervals
  for (let i = 0; i < intervals.length - 1; i++) {
    if (intervals[i][1] > intervals[i + 1][0]) {
      return false;
    }
  }
  
  return true;
}
 
// Test cases
console.log(canAttendMeetings([[0, 30], [5, 10], [15, 20]])); // false
console.log(canAttendMeetings([[7, 10], [2, 4]])); // true

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to determine if there are any overlapping meetings in the given intervals.
  2. 2. Identify the Brute Force Approach: The simplest approach is to check every pair of meetings to see if they overlap. Two meetings overlap if one starts before the other ends.
  3. 3. Implement the Brute Force Solution: Use nested loops to compare each meeting with every other meeting, checking for overlaps.
  4. 4. Analyze the Brute Force Solution: The brute force approach has O(n²) time complexity, which is not optimal for large inputs.
  5. 5. Optimize with Sorting: Sort the meetings by their start times, then check if each meeting ends before the next one starts.
  6. 6. Implement the Sorting Solution: Sort the intervals array and then iterate through it once, checking for overlaps between adjacent meetings.
  7. 7. Analyze the Sorting Solution: The sorting approach has O(n log n) time complexity, which is more efficient than the brute force approach.
  8. 8. Test with Examples: Verify the solution with the provided examples and edge cases.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone