Hello and welcome back brave human being.

Before we delve into the problem, I want to thank you for returning every day and working on your LeetCode skills.

There is no longer a concept of job security like our parents once had, but there is such concept of a me security. You are your best bet. You are your lottery ticket. Coming back to these problems is creating a better version of you.

So let’s get back into it.

You had two problems left on Wednesday, first a warm-up and then a slightly tougher one.

Day 13: Check if any two intervals intersect among a given set of intervals 

Given a set of intervals, check if any two intervals intersect.

The first approach would be to iterate interval by interval and check if an interval intersects. Is there a way to speed up this? Yes!!!

 Sorting!

We are going to sort based on start time, that way we can compare neighbors (intervals standing side by side) we decide if they overlap if the start time of an interval is less than the previous interval.

The full editorial can be found here.

Now that we have warmed up our brains, let’s move to another problem.

Day 14: 435. Non-overlapping Intervals

Given an array of intervals, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Now that we know the power of custom sorting, how can we leverage it for this problem?

Think about it, how do we sort it so we can identify which intervals are shorter?

We can sort them by the end time!

By sorting by end times and choosing intervals with earlier end time, you create more space for other intervals to fit in without overlapping. This "greedy" 💰 choice allows us to have more room for more intervals.

We can add it to an auxiliary vector and only add the intervals that don’t overlap.

Who can be in our vector?

We will be prioritizing intervals with earlier end time 💅 . Our first element in our vector is our greediest choice as this element has the earliest end time.

Once we get iterate over the intervals, our answer will be the delta (difference) between our original vector and our auxiliary vector.

Let’s dig in with an example:

Here is the complete solution:

What would be the time complexity?

Cheers to your weekend!

Denisse

RED FLAGS IN YOUR INTERVIEW SEARCH!