Interesting Intervals

                        Problems about Intervals 

   Always feel interested when deal with problems about intervals.  May be the feeling that you could visualize them in a 2D coordinates make me like them. Besides, after had few of them, you may feel they are not hard at all.

 Here is 4 examples about Intervals. Previous two are straightforward intervals, while the last two are more implicit.

           Example 1: Merge Intervals 

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

--------------------------------------------------------------------------------------------------------------------------

Analyze: Think about how you gonna approach this problem in general ( without any coding) ?

We probably will look through the whole input list and compare every adjacent two intervals, if they can be merged together then we merge them and look at next interval, or if can not be merged, we know that we will have this interval in our final output.

Two things need to notice before we start to implementing this idea:
  1. This idea only works when input intervals are in a sorted order.
  2. What we mean by saying " two intervals can be merged " ?

After figured out those two things, we may come up with a solution like below:

             Example 2 : Insert Intervals 

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

--------------------------------------------------------------------------------------------------------------------------

Analyze: Compare to the merge intervals question, this question provide already sorted interval for us, but one more interval will be insert into those sorted interval. We may come up with a very easy approach based on we already know how to solve problems like example 1.

Basically we could : 1. Insert while keep intervals sorted.
                                  2. Loop through the list, merge if necessary.




  Or if you like concise code

 

           Example 3: Meeting Rooms 1 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

--------------------------------------------------------------------------------------------------------------------------

Analyze: If you already go through previous 2 examples, this is a piece of cake for you !

The whole idea will be: if there is a meeting room start before a meeting even ended, then it is impossible to attend them all.

      Example 4: Meeting Room 2 

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

-----------------------------------------------------------------------------------------------------------------------

Analyze: In the example 3, we stop when we find one conflict ( start time early than end time) then stop. In this example, we could then translate this question into a another question where ask us how may conflict we have on those intervals. So try it out ! 

Update: 
 After you ever come up with this solution ? 

which is a little bit modification of meeting room 1 and we are really accounting how many conflict there are in the input.  However, there is one fact that if previous meeting is ended. We could then reuse the previous room !  Hence, that is why we need also sort the end time to know when we will get a previous room free to use. Here is the code with some explanation comments: 

Hope those 4 questions may help you to deal with Interval questions ! 

Happy Coding^^ 

Ye Jiang