Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Attend Meetings Problem

Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.

##### Input Format:

There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).

##### Output Format:

Return either a 1 or a 0.

#### Solutions

We have provided a solution which contains necessary comments to understand the approach used: solution.java

##### Description:

We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.

In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.

Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.

As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.

For better understanding, please have a look at the solution.

##### Time Complexity:

O(n log n) where n denotes the number of intervals.

As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).

##### Auxiliary Space Used:

O(1).

We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).

##### Space Complexity:

O(n) where n denotes the number of intervals.

To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).

``````
// -------- START --------
public static int canAttendAllMeetings(List> intervals){
// Sorting in ascending order of start value of an interval
// if start value is same for two intervals then sort in ascending order of end value of intervals
Collections.sort(intervals, new Comparator>() {
@Override
public int compare(List l1, List l2) {
if (l1.get(0) - l2.get(0)!= 0) {
return (int)(l1.get(0) - l2.get(0));
}
return (int)(l1.get(1) - l2.get(1));
}
});
// As intervals have at least one element
int previous_end = intervals.get(0).get(1);
for (int i=1; i intervals.get(i).get(0)) {
return 0;
}
// Updated previous' end.
previous_end = intervals.get(i).get(1);
}
return 1;
}
// -------- END --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Attend Meetings Problem

Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.

##### Input Format:

There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).

##### Output Format:

Return either a 1 or a 0.

#### Solutions

We have provided a solution which contains necessary comments to understand the approach used: solution.java

##### Description:

We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.

In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.

Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.

As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.

For better understanding, please have a look at the solution.

##### Time Complexity:

O(n log n) where n denotes the number of intervals.

As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).

##### Auxiliary Space Used:

O(1).

We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).

##### Space Complexity:

O(n) where n denotes the number of intervals.

To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).

``````
// -------- START --------
public static int canAttendAllMeetings(List> intervals){
// Sorting in ascending order of start value of an interval
// if start value is same for two intervals then sort in ascending order of end value of intervals
Collections.sort(intervals, new Comparator>() {
@Override
public int compare(List l1, List l2) {
if (l1.get(0) - l2.get(0)!= 0) {
return (int)(l1.get(0) - l2.get(0));
}
return (int)(l1.get(1) - l2.get(1));
}
});
// As intervals have at least one element
int previous_end = intervals.get(0).get(1);
for (int i=1; i intervals.get(i).get(0)) {
return 0;
}
// Updated previous' end.
previous_end = intervals.get(i).get(1);
}
return 1;
}
// -------- END --------
``````

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*