【数据结构实验笔记】空闲人数的最多时间段

HITSZ数据结构实验作业

我的做题经历,可以给大家一点点参考

首先输入两个数字N，M，表示N个空闲时间段，M个学生。接着程序输入M行，每行两个数字，表示第i名同学空闲时间的开始时间段与终止时间段。其中1≤N≤100000000 ， 1≤M≤1000。
程序输出成对的数字，表示空闲人数最多时间段的起始时间和终止时间，如若有多对，请以递增形式在一行中输出。不同对之间用英文逗号“,”分隔，对内元素用空格隔开。
当两个时间段的空闲学生不完全一致时，我们认为其为不同时间段。如若完全一致，则为相同时间段。
要求：排序算法的平均时间复杂度不得大于O(Mlog₂M)。

直接使用长度为n的线性表表示各个时间点是最容易想到的办法,但是这样需要的空间非常非常大,并且时间复杂度也远大于要求.

进一步分析,如果按照上述建立存储结构,那么数组中间有很多部分其实是相等的,人数真正发生变化的时间点其实就是我们每次输入的同学起始时间和终止时间.我们可以认为在后m行输入的这些时间点是关键时间点,我们只需要分析这些时间点即可.

IN数组表示各个起始时间

OUT表示各个终止时间

typedef struct Time
{
    int mark;//时间点的位置
    int pop;//该点的人数
} Time;

注意:终止时间点的下一个时间点才是人数减少的时间点

    int n, m; // n:接受时间段,m接受学生数量(其实n没什么用)
       //输入
    scanf("%d", &n);
    scanf("%d", &m);
    int counter = 0;
    for (counter = 0; counter < m; counter++)
        scanf("%d %d", &In[counter], &Out[counter]);

使用任意方法将IN数组和OUT数组进行排序即可

如果不排序,那么我们寻找关键时间点并进行操作时则必须要建立一个一一对应的key.

归并这两个数组的原因:得到一个Schedule数组,这个数组存储的信息就是所有人数发生变化的时间点,之后我们只需要按照顺序,将Schedule表与IN以及OUT分别比较即可.

timelist : Time结构体数组,存储的是关键时间点

将schedule数组里重复的元素删除得到changetime数组,可以把changetime当作一串指令,指令内容如下

• 如果changtime[n]与IN [i] 相同,那么将IN[i]记录为timelist[counter++].mark,人数timelist[counter-1].pop+1(如果有重复那么则自加);
• 如果changetime[n]与OUT[j]相同,那么OUT[j]记录为timelist[counter+1].mark,人数为timelist[counter].pop-1(如果有重复那么则自减);

略过

第五步我们已经找出所有人数最多的关键点

那么输出就非常简单了.

人数最多的关键点到下一个关键点的前一个点就是人数最多的时间段,直接输出即可.

1. 当两个时间段的空闲学生不完全一致时，我们认为其为不同时间段。如若完全一致，则为相同时间段。这个要求如何实现?

   我们仔细分析就可以发现,因为每次输入IN,OUT时都是不同的同学,那么说明不同关键点中包含的学生绝对不可能相同

   举个例子:

   假设

   pop	mark
   timelist[2].pop=10 (max)	timelist[2].mark=2
   timelist[3].pop=10 (max)	timelist[3].mark=5
   timelist[4].pop=4	timelist[4].mark=6

   timelist[2],timelist[3]这两个点都被选作关键点,说明在timelist[2]之后走了一部分人,在timelist[3]中又进来了相等数量的其他人,所以可以认为是不同的时间段.输出时就是2 4, 5 5

完整代码:

#include 
#include 

#define MAX_STUDENT 1000
typedef struct Time
{
    int mark;
    int pop;
} Time;



void Combine(int a[], int b[], int c[], int length)
{
    int i = 0, j = 0, k = 0;
    while (i < length && j < length)
        c[k++] = a[i] < b[j] ? a[i++] : b[j++];
    while (i < length)
        c[k++] = a[i++];
    while (j < length)
        c[k++] = b[j++];
}

void FindMax(int in[], int out[], int schedule[], int length)
{
    int counter = 0, i = 0, j = 0, k = 0, n = -1;

    Time *timelist; //记录时间点
    timelist = (Time *)malloc(sizeof(Time) * length * 2);
    //对时间点初始化
    //省略

    int *changetime; //记录发生变化的时间点
    changetime = (int *)malloc(sizeof(int) * length*2);
    for (counter = 0, i = -1; counter < 2 * length; counter++)
    {
        if (i == -1)
            changetime[++i] = schedule[0];
        else if (changetime[i] != schedule[counter])
            changetime[++i] = schedule[counter];
    }
    
    //找出所有关键点,并且对每个关键点进行赋值
    for (counter = 0; counter <= i; counter++)
    {
        if (changetime[counter] == in[j])
        {
            if (timelist[n].mark != in[j] && j < length)
            {
                n++;
                if (n > 0)
                    timelist[n].pop = timelist[n - 1].pop;
                else if (n == 0)
                    timelist[n].pop = 0;
                timelist[n].mark = in[j];
                while (changetime[counter] == in[j])
                {
                    timelist[n].pop++;
                    j++;
                }
            }
            else
                while (changetime[counter] == in[j])
                {
                    timelist[n].pop++;
                    j++;
                }
        }
        if (changetime[counter] == out[k] && k < length)
        {
            timelist[n + 1].pop = timelist[n].pop;
            while (out[k] == changetime[counter] && k < length)
            {
                k++;
                timelist[n + 1].mark = changetime[counter] + 1;
                timelist[n + 1].pop--;
            }
            n++;
        }
    }
    
    //最终timelist内部有n个关键时间点
    //下面找出所有关键时间点中最大的数
    int max = timelist[0].pop;
    for (counter = 1; counter <= n; counter++)
    {
        if (timelist[counter].pop > max)
            max = timelist[counter].pop;
    }

    //输出 分成两步是为了逗号
    for (counter = 0; counter <= n; counter++)
    {
        if (timelist[counter].pop == max)
        {
            printf("Result:n%d %d", timelist[counter].mark, timelist[counter + 1].mark - 1);
            break;
        }
    }
    counter++;
    for (; counter <= n; counter++)
    {
        if (timelist[counter].pop == max)
        {
            printf(",%d %d", timelist[counter].mark, timelist[counter + 1].mark - 1);
        }
    }
}

int main()
{
    // in数组
    // out数组
    //数组使用归并排序

    int In[MAX_STUDENT];
    int Out[MAX_STUDENT];
    int Schedule[2 * MAX_STUDENT];
    int n, m; // n:接受时间段,m接受学生数量
              //输入
    scanf("%d", &n);
    scanf("%d", &m);
    int counter = 0;
    for (counter = 0; counter < m; counter++)
        scanf("%d %d", &In[counter], &Out[counter]);

    //排序
    //排序算法可以自己选择自己熟悉的,就不列出来了
    Sort(In, m);
    Sort(Out, m);
    //归并
    Combine(In, Out, Schedule, m);

    //找出最大时间点
    FindMax(In, Out, Schedule, m);

    return 0;
}