This afternoon, several TopCoder members independently ate lunch at the prestigious TopCoder cafe. They each arrived and left at different times, and nobody returned to the cafe after having left once. Throughout the day, TopCoder waiters noticed that certain members saw each other in the cafe and shook hands. This information was collected in the form of a String[] M, where M[i][j] is '1' if member i and member j were seen to shake hands. Otherwise, M[i][j] is '0'. Clearly, if M[i][j] is '1', then members i and j must have been at the cafe at overlapping times. On the other hand, certain TopCoder members do not know each other, so they might not have shaken hands even if they were at the cafe at overlapping times. Given this information, TopCoder is interested in estimating the largest number of people who were in the cafe at one time.
Create a class LunchScheduler that contains a method getOverlap, which is given a String[] M, as described above. It should return an int, specifying the largest integer k such that at least k members must have been in the cafe together at one time.
Suppose, for example,
M = {"0110",
"1010",
"1100",
"0000"}.
Then, two possible lunch schedules are shown below.
Member | Time period Member | Time period
-------+----------------- -------+-----------------
1 | *************** 1 | *******
2 | *************** 2 | *******
3 | *********** 3 | ***
4 | ****** 4 | *****
Here, the *'s indicate the time periods during which each member was in the cafe. As can easily be checked, both schedules are consistent with M. The leftmost schedule has four members in the cafe at one time, but this is not necessary, as can be seen from the fact that the rightmost schedule never has more than three people together at once. It turns out that any other valid schedule will also have at least three members in the cafe at one time, so the correct value for k is 3 in this case. |