TopCoder problem "Switching" used in TCCC05 Semi 2 (Division I Level Two)



Problem Statement

    We have run some processes concurrently on a single cpu by time sharing. Only one process could run at a time, but the operating system often switched which of the processes was the one that was running.

Each process, as it ran, frequently checked what time it was and stored that time. The sequence of times that each process observed is given to us. We want to find out how often the context was switched from one of our processes to another. Because it is possible that a process was allowed to execute very briefly and then the cpu was switched to a different process before the first process checked and stored the time, the best we can hope for is to find the minimum possible number of switches that is consistent with the recorded times.

The biggest complication is that times on a computer are discrete. If the time that was recorded was 3, that means that the actual time was sometime between the third and fourth clock tick. Multiple processes could record the same time, and one process could record the same time multiple times.

Create a class Switching that contains a method minSwitch that is given String[] ticks, the sequence of times recorded by each process, and that returns the smallest number of context switches that could have occurred. The i-th element of ticks contains the sequence of times recorded by the i-th process.

 

Definition

    
Class:Switching
Method:minSwitch
Parameters:String[]
Returns:int
Method signature:int minSwitch(String[] ticks)
(be sure your method is public)
    
 

Constraints

-ticks will contain between 2 and 50 elements inclusive.
-Each element of ticks will contain between 1 and 50 characters, inclusive.
-Each element of ticks will consist of integer values separated by single spaces.
-No element of ticks will have leading or trailing spaces.
-Each value of each element ticks will be between 1 and 20000 inclusive.
-The values within each element of ticks will be in non-decreasing order.
-The values within each element of ticks will have no leading zeroes.
 

Examples

0)
    
{"3 5 7 7 8","4 6 7 7 12"}
Returns: 5
The only possible order in which these 2 processes (A and B) could have run with only 5 context switches is: A during 3, B during 4, A during 5, B during 6 and 7, A during (a later part of)7 and 8, B during 12. (We can't tell which one was running during 9,10, and 11 but the last switch could have occurred anywhere from late in 8 to early in 12.)
1)
    
{"3 3 3 3 3","3 3 3 3 3"}
Returns: 1
They could have switched back and forth during 3, but it is possible that one of them ran completely first during 3, and then the other ran entirely during a later part of 3.
2)
    
{"3 3 3 4 4 7 8 8 9","3 5 6 7 7 8 10","3 4 4 5 8 9 10"}
Returns: 10
Here is one possible order: B3, C3, A3-4, C4-5, B5-7, A7-8, B8, C8, A9, C9-10, B10. Note that there are 11 separate runs, so 10 switches.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6551&pm=3933

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Dynamic Programming, Greedy