Type 1:

Merge Interval

In this Question,

Step 1:Sort according to their starts, which means sort in ascending order.

Step 2: And while we are merging we just check the

second start element is <= the previous list end element.

If this condition satisfy then we will update the end=max(first_list_end_element,second_list_end_element)

else the intervals are disjoint hence simply add the current Interval without making any changes to the previous interval.

For example, given the intervals [1,3], [2,6], [8,10], [15,18], the function should return [[1,6], [8,10], [15,18]] because [1,3] and [2,6] overlap and are merged into [1,6].

Here's how the merging process works:

• Start with the first interval, [1,3].

• Keep track of the start and end values of the interval, which are initially set to 1 and 3, respectively.

• Move on to the next interval, [2,6].

• Since 2 is between 1 and 3, the intervals overlap and we need to merge them.

• Update the end value of the current interval to the maximum of the previous interval's end value (3) and the current interval's end value (6), which is 6.

• Repeat this process for the remaining intervals, updating the start and end values as needed.

• Finally, return the merged intervals.

TC: O(n log n) + O(n) = O(n log n), SC:O(n)

TYPE 2:

INSERT INTERVAL

This is slightly more tricky than merge intervals though we use the same concept.

We have to Find the index whose start is as close to or exactly equal to the start of the new interval

For example, given the intervals = [1,2], [3,5], [6,7], [8,10],[12,16], and the newInterval= [4,8]the function should return [1,2], [3,10], [12,16] because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Here's how the merging process works:

• Start with the first interval, [1,2].

• We Loop through the intervals array and add all non-overlapping intervals to the merge list.

• i=0 [1,2]

  interval[0][1]=2 newInterval[0]=4

  2<4 we can add [1,2] to the list

• i=1 [3,5].

  interval[0][1]=5 newInterval[0]=4

  5<4 condition not satisfied we will come out of the while loop

• 

• This loop checks for all intervals that overlap with the new interval, merges them with the new interval, and updates the new interval accordingly. Once all overlapping intervals have been merged, we add the new interval to the merge list.

• i=1 [3,5]

  interval[1][0]=3 newInterval[1]=8

  3<=8

  newInterval[0]=min(4,3) which is 3

  newInterval[1]=max(8,5) which is 8

• i=2 [6,7]

  interval[2][0]=6 newInterval[1]=8

  6<=8

  newInterval[0]=min(3,6) which is 3

  newInterval[1]=max(8,7) which is 8

• i=3 [8,10]

  interval[3][0]=8 newInterval[1]=8

  8<=8

  newInterval[0]=min(3,8) which is 3

  newInterval[1]=max(8,10) which is 10

• i=4 [12,16]

  interval[4][0]=12 newInterval[1]=10

  12<=10 conditions fail we will come out of the while loop

  

• Add any remaining non-overlapping intervals to the merge list

TC:O(n) SC:O(n)

TYPE 3:

Minimum Number of Platforms Required for a Railway Station

In this question, we have Given the arrival and departure times of all trains that reach a railway station. We have to find the minimum number of platforms required for the railway station so that no train is kept waiting and all the trains arrive on the same day and leave on the same day and the same platform can not be used for both departures of a train and arrival of another train. In such cases, we need different platforms

arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}

dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

Output: 3

Minimum 3 platforms are required to safely arrive and depart all trains.

How? let's find out

Step 1: first we have to sort the arrival time and departure time

it will become like this.

arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}

dep[] = {9:10, 11:20, 11:30, 12:00, 19:00, 20:00}

so whenever there is a conflict of arr and dept time we have to increase the number of platforms.

Step2 :

i = 1, j = 0, max = 1, plat = 1

arr[1]=9:40 dept[0]=9:10

9:40<=9:10 ❌ i=1 j=1 max=1 plat=0

9:40<=11:20 ✅ i=1 j=1 max=1 plat=1

9:50<=11:20 ✅ i=2 j=1 max=2 plat=2

11:00<=11:20 ✅ i=3 j=1 max=3 plat=3

15:00<=11:20❌ i=4 j=2 max=3 plat=2

15:00<=11:30❌ i=4 j=2 max=3 plat=1

15:00<=12:00❌ i=4 j=3 max=3 plat=0

15:00<=19:00✅ i=4 j=4 max=3 plat=1

18:00<=19:00 ✅ i=5 j=4 max=3 plat=2

so the maximum platform is 3

TC:O(nlogn) SC:O(1)