TIANKENG’s restaurant

<span size="+0"><strong><span style="font-family:Arial;font-size:12px;color:green;FONT-WEIGHT: bold">Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)Total Submission(s): 664    Accepted Submission(s): 311</span></strong></span>

Problem Description

TIANKENG manages a restaurant after graduating from ZCMU, and tens of thousands of customers come to have meal because of its delicious dishes. Today n groups of customers come to enjoy their meal, and there are Xi persons in the ith group in sum. Assuming that each customer can own only one chair. Now we know the arriving time STi and departure time EDi of each group. Could you help TIANKENG calculate the minimum chairs he needs to prepare so that every customer can take a seat when arriving the restaurant?

<span style="font-size:14px;"></span>

Input

The first line contains a positive integer T(T<=100), standing for T test cases in all.Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time.Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough.

<span style="font-size:14px;"></span>

Output

For each test case, output the minimum number of chair that TIANKENG needs to prepare.

<span style="font-size:14px;"></span>

Sample Input

226 08:00 09:005 08:59 09:5926 08:00 09:005 09:00 10:00

<span style="font-size:14px;"></span>

Sample Output

116

<span style="font-size:14px;"></span>

Source

BestCoder Round #2 

<span style="font-size:14px;">题意：在给定一段时间内的人数，又给你了这段时间区间的明确范围，让你确定，要满足所有人来了都有位子坐，至少需要多少位子。</span>

<span style="font-size:14px;">思路：这道题可以用标记模拟法，求出那段区间的明确范围，然后将没一分钟，均设置为n个人这样后来的数据就是在n的基础上相加即可，最后，进行遍历，找出从零到设置的数组的最大范围，求出最大值，即是需要准备的最少的位子。</span>

<span style="font-size:14px;">#include<stdio.h>#include<string.h>int main(){	int n,j,max;	int a[1600];	int i,m,t,h1,h2,m2,m1;	int sum1,sum2;	scanf("%d",&n);	while(n--)	{		scanf("%d",&m);		memset(a,0,sizeof(a));		for(i=0;i<m;i++)		{			scanf("%d %d:%d %d:%d",&t,&h1,&m1,&h2,&m2);			sum1=h1*60+m1;			sum2=h2*60+m2;			for(j=sum1;j<sum2;j++)			{				a[j]+=t;			}		}		max=a[0];		for(i=0;i<1600;i++)		{			if(max<a[i])			max=a[i];		}		printf("%d\n",max);	}	return 0;}</span>