【算法设计】计算某个时间段的至多参会人数

【算法设计】计算某个时间段的最多参会人数

本帖最后由 liyudefly 于 2013-12-27 14:39:31 编辑

假设会议从开始到结束共S分钟，会议过程中随时可以有人加入，也随时可以有人退出，进入和退出的时间均有记录，现将会议分成X段，求每段内最多在一起开会的人数。
例如有个会议125分钟，分成了0~30，31~60，61~90，91~120，120~125这五段，即30，60，90，120这四个分割点，第一人3分钟进来，50分钟退出，第二人4分钟进来，一直到会议结束，第三人7分钟进来，20分钟退出，第四人15分钟进来80分钟退出，第五人25分钟进来，一直开到最后，那么每段内最多同时在开会的人数为：0~30，4人，31~60，4人，61~90，3人，91~120，2人，120~125,2人。
若有不清楚的地请提问，第一时间补充说明，分最多给两人，复制过来的可以，我没找到。。。

------解决方案--------------------
如果出现就算,那么例子里第一时间段应该是5人
------解决方案--------------------
这不就是最大连续字串之和问题吗？
把每条进出记录作为一个数组元素，进人则正值，出人则为负值，总时间分为几段把记录分为几个数组，每个数组第一个元素为进入该时间段前会议室人数。使用类似动态规划扫描算法，复杂度O(n);
附上之前写的扫描算法：

#include <stdio.h>

int max_sub_sum(int *a , int n)

{

	int max_sofar = a[0];

	int max_with_i = a[0];

	int i;


	for(i=1;i<n;i++)

	{

		max_with_i = max_with_i<0?a[i]:max_with_i+a[i];

		max_sofar = max_sofar>max_with_i?max_sofar:max_with_i;

	}

	return max_sofar;


}


int main()

{

	int a[]={-31,-41,-59,-26,53,-58,97,93,-23,-84,-23,-44,-56};

	int max_sub;

	max_sub = max_sub_sum(a,sizeof(a)/sizeof(int));

	printf("%d\n",max_sub);

	return 0;

}

------解决方案--------------------

// 时间段杖举

enum EnTimeSeg

{

	EnFirstSeg,

	EnSecondSeg,

	EnThirdSeg,

	EnFourthSeg,

	EnFifthSeg

};


// 每个时间段的数据，其实可以直接用int 数组就OK了

struct STRU_SegInfo

{

	EnTimeSeg enSeg;

	int nMaxPerson;

};


struct STRU_SegInfo[5];

STRU_SegInfo[0].enSeg = EnFirstSeg,  STRU_SegInfo[0].nMaxPerson = 0;

STRU_SegInfo[1].enSeg = EnSecondSeg, STRU_SegInfo[1].nMaxPerson = 0;

STRU_SegInfo[2].enSeg = EnThirdSeg,  STRU_SegInfo[2].nMaxPerson = 0;

STRU_SegInfo[3].enSeg = EnFourthSeg, STRU_SegInfo[3].nMaxPerson = 0;

STRU_SegInfo[4].enSeg = EnFifthSeg,  STRU_SegInfo[4].nMaxPerson = 0;


// 用死循环处理这个东西很不好

while (1)

{

	// 判断有人进还是有人出

	{

		// 获取当前时间，判断属性哪个时间段

		// 如果是有人出则将当前时间段下nMaxPerson 减一

		// 如果是有人进则将当前时间段下nMaxPerson 加一

	}

}

------解决方案--------------------
我只会用最笨的办法：

//假设会议从开始到结束共S分钟，会议过程中随时可以有人加入，也随时可以有人退出，进入和退出的时间均有记录，

//现将会议分成X段，求每段内最多在一起开会的人数。

//例如有个会议125分钟，分成了0~30，31~60，61~90，91~120，120~125这五段，即30，60，90，120这四个分割点，

//第一人3分钟进来，50分钟退出，

//第二人4分钟进来，一直到会议结束，

//第三人7分钟进来，20分钟退出，

//第四人15分钟进来80分钟退出，

//第五人25分钟进来，一直开到最后，

//那么每段内最多同时在开会的人数为：

//0~30，4人，

//31~60，4人，

//61~90，3人，

//91~120，2人，

//120~125,2人。

#include <stdio.h>

static char d[5][125];

int h[5][2]={

    {  3, 50},

    {  4,124},

    {  7, 20},

    { 15, 80},

    { 25,124},

};

int g[5][2]={

    {  0, 30},

    { 31, 60},

    { 61, 90},

    { 91,120},

    {120,124},

};

int i,j,k,m,m1;

int main() {

    for (i=0;i<5;i++) {

        for (j=h[i][0];j<=h[i][1];j++) d[i][j]=1;

    }

    for (k=0;k<5;k++) {

        printf("%d~%d,",g[k][0],g[k][1]);

        m1=0;

        for (j=g[k][0];j<=g[k][1];j++) {

            m=0;

            for (i=0;i<5;i++) {

                m+=d[i][j];

            }

            if (m>m1) m1=m;

        }

        printf("%d\n",m1);

    }

    return 0;

}

//0~30,4

//31~60,4

//61~90,3

//91~120,2

//120~124,2

//

【算法设计】计算某个时间段的至多参会人数

相关推荐