DSA Visualizations | Hello Interview

Limited Time Offer: 40% off Hello Interview Premium 🎉

40% off Hello Interview Premium 🎉

Back to Main

Learn DSA

Overview

Two Pointers

Sliding Window

Intervals

Stack

Linked List

Binary Search

Heap

Depth-First Search

Breadth-First Search

Backtracking

Graphs

Dynamic Programming

Greedy Algorithms

Trie

Prefix Sum

Matrices

Pricing

Become a Coach

Pricing Become a Coach

Get Premium

Overview

Insert Interval

Can Attend Meetings

DESCRIPTION (credit Leetcode.com)

Write a function to check if a person can attend all the meetings scheduled without any time conflicts. Given an array intervals, where each element [s1, e1] represents a meeting starting at time s1 and ending at time e1, determine if there are any overlapping meetings. If there is no overlap between any meetings, return true; otherwise, return false.

Note that meetings ending and starting at the same time, such as (0,5) and (5,10), do not conflict.

EXAMPLES

Input:


intervals = [(1,5),(3,9),(6,8)]

Output:


false

Explanation: The meetings (1,5) and (3,9) overlap.

Input:


intervals = [(10,12),(6,9),(13,15)]

Output:

true

Explanation: There are no overlapping meetings, so the person can attend all.

Run your code to see results here

Explanation

A person can attend all meetings if and only if none of the meetings overlap. By sorting the intervals by start time, we can easily check if any two consecutive intervals overlap.

We iterate over each interval, beginning with the second interval in the sorted list. We compare the start time of the current interval with the end time of the previous interval. If the start time of the current interval is less than the end time of the previous interval, then the two intervals overlap and the person cannot attend both meetings, so we return false.

Two overlapping meeting intervals

Otherwise, the person can attend both meetings, and we continue to the next interval. If we reach the end of the list without finding any overlapping intervals, then the person can attend all meetings, and we return true.

Solution


def canAttendMeetings(intervals):
  intervals.sort(key=lambda x: x[0])

  for i in range(1, len(intervals)):
    if intervals[i][0] < intervals[i - 1][1]:
      return False

  return True

can attend meetings

0 / 5

Complexity Analysis

Time Complexity: O(n * logn) where n is the number of intervals due to the sorting step. Space Complexity: O(1) since we are not using any extra space.

Next: Insert Interval

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103