TopCoder problem "OlympicsBroadcasting" used in TCCC06 Semi 2 (Division I Level One)



Problem Statement

    

You are running a TV network that has the rights to transmit the olympic games. The network is going to create several channels that transmit events of the games continuously. Few rules have been established for these new channels:

  • Each event cannot be transmitted on more than one channel
  • Any part of an event may be included in the scheduled programming, even if the beginning and/or the end of it are excluded, but at most one interval of the event can be shown
  • Each channel must have a continuous transmission

You will be given the schedule of the olympics in 2 int[]s startingTime and endingTime, with the ith element of startingTime and endingTime representing the starting and ending time of the ith scheduled event in a special time unit (each interval contains both endpoints, see examples for further clarification). The duration of the games is exactly totalUnits of this time units, which means that the transmition of all the created channels must start at time 0 and end at time totalUnits. Return the maximum number of channels that can be created while satisfying these network policies.

 

Definition

    
Class:OlympicsBroadcasting
Method:getMaxChannels
Parameters:int[], int[], int
Returns:int
Method signature:int getMaxChannels(int[] startingTime, int[] endingTime, int totalUnits)
(be sure your method is public)
    
 

Constraints

-startingTime will have between 1 and 50 elements, inclusive.
-startingTime and endingTime will have the same number of elements.
-totalUnits will be between 1 and 1000000000 (109), inclusive.
-Each element of startingTime and endingTime will be between 0 and totalUnits, inclusive.
-The ith element of endingTime will be greater than the ith element of startingTime.
 

Examples

0)
    
{0,1,1,1,0}
{2,2,3,3,3}
3
Returns: 2
We can make 2 channels:
  1. Event with index 0 from time 0 to time 2 and event 2 from 2 to 3.
  2. Event with index 4 from time 0 to time 3.
1)
    
{0}
{1000}
1000
Returns: 1
2)
    
{0,1,2,3,4}
{1,2,3,4,5}
5
Returns: 1
3)
    
{0,4,8}
{3,9,12}
12
Returns: 0
There is no way to cover the 3-4 interval.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6461

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10133&pm=6461

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , Jan_Kuipers

Problem categories:

Greedy, Sorting