This post is completed by 2 users

  • 1
 Add to List
Beginner

494. Check if the given playlist of programs is valid

Problem Statement:

Given a playlist that contains the list of intervals with the start time, end time and program id. Write a program to validate whether the playlist is valid or not based on certain conditions. 

The playlist will be considered invalid if any of the following is true -

  • If any two programs overlap.
  • If there is any gap between two intervals.
  • If the duration of any program is less than 10.
  • If the duration of any program is greater than 200.
  • If the duration of any program is negative.
  • If the start time or end time of any program is negative.

If none of the above is true then play list is valid else playlist is not valid. In the case of an invalid playlist, also print the reason with program id. 

Example:

Playlist =
[[111, 0, 10],
[222, 100, 300],
[333, 300, 350],
[444, 10, 30],
[555, 30, 100]]
Note: [id, start_time, end_time]
Output: Given playlist is valid

Playlist:
[[111, 0, 10],
[444, 10, 15],
[555, 13, 17],
[333, 20, 100],
[222, 150, 350],
[666, 350, -450]]
Output:
Given playlist is NOT valid due to following reasons -
Program Id: 444 has duration less than 10
Program Id: 555 has duration less than 10
Program Id: 444 and Id: 555 are overlapping
Program Id: 444 and Id: 555 are having gap
Program Id: 555 and Id: 333 are having gap
Program Id: 333 and Id: 222 are having gap
Program Id: 666 has negative times
Program Id: 666 has negative duration
Program Id: 666 has duration less than 10

Approach:

Sort all the programs in the playlist in ascending order of their start time.

Now iterate through programs from left to right and for each program check the duration and timings as per given conditions and compare every adjacent pair of programs for any overlapping (if the start time of the next program is less than the end time of the current program) or for any gap (if the start time of next program is greater than the end time of current program). Keep collecting all the outcomes in a list with program id and at the end, print the list.

Time Complexity: O(nlogn)

 

Output:

Given playlist is valid
-----------------------------------------------
Given playlist is NOT valid due to following reasons -
Program Id: 444 has duration less than 10
Program Id: 555 has duration less than 10
Program Id: 444 and Id: 555 are overlapping
Program Id: 444 and Id: 555 are having gap
Program Id: 555 and Id: 333 are having gap
Program Id: 333 and Id: 222 are having gap
Program Id: 666 has negative times
Program Id: 666 has negative duration
Program Id: 666 has duration less than 10
-----------------------------------------------

Related Problems: