TopCoder problem "OfficeParking" used in SRM 187 (Division II Level One)



Problem Statement

    

The TopCoder office building is filled with very efficient people. Each of these people always parks their car in the closest (to the building) available parking space. The parking spaces are arranged linearly, with space number one being the closest to the building, space number two being the second closest to the building, etc.

Given a sequence of employee arrivals and departures, determine the number of parking spaces used that day. The parking lot is empty at the beginning of the day. Names are case sensitive.

For example in the sequence of events below:

{"Alice arrives",
 "bob arrives",
 "Alice departs",
 "Charles arrives",
 "bob departs",
 "Charles departs"}

Alice parks in space 1
bob parks in space 2
Alice vacates space 1
Charles parks in space 1
bob vacates space 2
Charles vacates space 1

The total number of parking spaces used is 2.

 

Definition

    
Class:OfficeParking
Method:spacesUsed
Parameters:String[]
Returns:int
Method signature:int spacesUsed(String[] events)
(be sure your method is public)
    
 

Notes

-HINT: If the maximum number of people at the office building at once is N, then there is never a reason for anyone to park in the (N+1)st spot, as one of the first N spots must have been available when they arrived.
 

Constraints

-events will have between 0 and 50 elements inclusive.
-Each element of events must contain between 9 and 50 characters, inclusive.
-Each element of events is formatted as "<name> <action>" (quotes for clarity).
-Each <name> contains between 1 and 42 characters, inclusive.
-Each <name> contains only letters ('a'-'z', 'A'-'Z').
-Each <name> and <action> are separated by exactly one space character.
-Each <action> is either "arrives" or "departs".
-Departures will always have a matching arrival (with the exact same case sensitive name) in a previous element of events.
-There will not be two arrivals of the exact same case sensitive name without an intervening departure of the exact same name.
 

Examples

0)
    
{"Alice arrives","bob arrives","Alice departs",
 "Charles arrives","bob departs","Charles departs"}
Returns: 2
The example above.
1)
    
{"AdminBrett arrives","lbackstrom arrives","AdminBrett departs","mike arrives",
 "TheFaxman arrives","AdminBrett arrives","lbackstrom departs","dok arrives",
 "AdminBrett departs","gt arrives","AdminBrett arrives","lbackstrom arrives",
 "AdminBrett departs","jhughes arrives","jhughes departs","TheFaxman departs",
 "MaryJoe arrives","AdminBrett arrives","AdminBrett departs","AdminBrett arrives"}
Returns: 6
2)
    
{"SnapDragon arrives","tomek arrives","JohnDethridge arrives","ZorbaTHut arrives",
 "snewman arrives","reid arrives","NGBronson arrives","Yarin arrives",
 "bstanescu arrives","mathijs arrives","radeye arrives","bladerunner arrives",
 "dgarthur arrives","venco arrives","dmwright arrives","WishingBone arrives",
 "Eryx arrives","antimatter arrives","ChristopherH arrives","lars arrives",
 "biggnate arrives","JanKuipers arrives","dary arrives","haha arrives","grotmol arrives",
 "XuChuan arrives","Ryan arrives","LunaticFrindge arrives","Wasteland arrives",
 "RunningWild arrives","hampster arrives","RalphFurmaniak arrives",
 "kyky arrives","qubits arrives","Rustyoldman arrives","turuthok arrives",
 "Vulpecular arrives","Eeyore arrives","wackes arrives","Ishan arrives",
 "dimkadimon arrives","dplass arrives","Olorin arrives","TangentZ arrives",
 "NeverMore arrives","Pops arrives","srowan arrives","tjq arrives",
 "vorthys arrives","schveiguy arrives"}
Returns: 50
3)
    
{"AdminBrett arrives","AdminBrett departs","AdminBrett arrives","AdminBrett departs",
 "AdminBrett arrives","AdminBrett departs","AdminBrett arrives","AdminBrett departs",
 "AdminBrett arrives","AdminBrett departs","AdminBrett arrives","AdminBrett departs",
 "AdminBrett arrives","AdminBrett departs","AdminBrett arrives","AdminBrett departs"}
Returns: 1
4)
    
{"snapdragon arrives","SnapDragon arrives",
 "AdminBrett arrives","AdminBrett departs",
 "SnapDragon departs","snapdragon departs"}
Returns: 3
5)
    
{"departs arrives","arrives arrives","arrives departs","departs departs"}
Returns: 2
Note that the first words are the names, and the second words are the actions.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4755&pm=2400

Writer:

Rustyoldman

Testers:

lbackstrom , brett1479

Problem categories:

Simulation