Skip to content

Latest commit

 

History

History
140 lines (106 loc) · 3.85 KB

12(Nov) Meeting Rooms.md

File metadata and controls

140 lines (106 loc) · 3.85 KB
Raw

12. Meeting Rooms

The problem can be found at the following link: Problem Link

Note: I'm currently in the middle of my exams until November 19, so I’ll be uploading daily POTD solutions, but not at a fixed time. Apologies for any inconvenience, and thank you for your patience!

Problem Description

Given an array arr[][], where arr[i][0] is the starting time of the i-th meeting and arr[i][1] is the ending time of the i-th meeting, determine if it is possible for a person to attend all the meetings. A person can only attend one meeting at a time, meaning each meeting must start after the previous one ends.

Examples:

Input:

arr[][] = [[1, 4], [10, 15], [7, 10]]

Output:

true

Explanation:
Since all the meetings are held at different times, it is possible to attend all the meetings.

Input:

arr[][] = [[2, 4], [9, 12], [6, 10]]

Output:

false

Explanation:
The second and third meetings overlap, making it impossible to attend all of them.

My Approach

  1. Sorting and Overlap Checking:

    • First, sort the meetings based on their starting times.
    • Traverse through the sorted list, comparing the end time of the current meeting with the start time of the next meeting.
    • If any meeting starts before the previous one ends, return false as overlapping prevents attending all meetings.

  2. Edge Cases:

    • If there are no meetings, return true.
    • If there is only one meeting, return true as no overlap can occur.

Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(n log n), where n is the number of meetings. Sorting the list of meetings takes O(n log n), while checking overlaps requires O(n).
  • Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space to store indices and temporary values.

Code (C++)

class Solution {
  public:
    bool canAttend(vector<vector<int>>& arr) {
        int n = arr.size();
        sort(arr.begin(), arr.end());
        for (int i = 0; i < n - 1; i++) {
            if (arr[i][1] > arr[i + 1][0])
                return false;
        }
        return true;
    }
};

👨‍💻 Alternative Approaches

Alternative Approach (Using Lambda Comparator)

class Solution {
public:
    bool canAttend(std::vector<std::vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i - 1][1] > intervals[i][0]) {
                return false;
            }
        }
        return true;
    }
};

Code (Java)

class Solution {
    static boolean canAttend(int[][] arr) {
        Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0])); 
        
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i][1] > arr[i + 1][0]) { 
                return false;
            }
        }
        return true; 
    }
}

Code (Python)

class Solution:
    def canAttend(self, arr):
        arr.sort(key=lambda x: x[0])  
        for i in range(len(arr) - 1):
            if arr[i][1] > arr[i + 1][0]:  
                return False
        return True

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count