讨论/求职面试/面试算法题/

遇到一道算法题,各大佬能帮解释一下吗?感谢!

假设设计了一个多线程并发请求的任务,知道每一个请求发起的时间和结束的时间,以秒为单位,同时知道App启动会发起请求的总数量,如何快速计算出哪一秒里并发请求的任务是最多的,时间复杂度和空间复杂。

12
共 2 个回复

根据零神的回答,写出如下C代码:

typedef struct __taskInfo {
    int taskId; // 任务ID
    int start;  // 起始时间
    int end;    // 结束时间
}TaskInfo;

// 时间选项
enum OP{
    start = 0,  // 起始
    end   = 1,  // 结束
};

typedef struct __taskData{
    int taskId;     // 任务ID
    int timestamp;  // 时间
    enum OP op;     // 时间类型
}TaskData;


int max(int a, int b)
{
    return a > b ? a : b;
}

// 根据「时间」进行「快速」排序
void quickSort(TaskData datas[], int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int tempL = left;
    int tempR = right;
    TaskData base = datas[tempL];
    while (tempL < tempR)
    {
        while (tempL < tempR && datas[tempR].timestamp > base.timestamp)
        {
            tempR--;
        }
        datas[tempL++] = datas[tempR];
        while (tempL < tempR && datas[tempL].timestamp < base.timestamp)
        {
            tempL++;
        }
        datas[tempR--] = datas[tempL];
    }
    datas[tempL] = base;
    quickSort(datas, left, tempL - 1);
    quickSort(datas, tempR + 1, right);
}

// 求解「最大」任务数
int maxTaskCount(TaskInfo tasks[], int tasksSize)
{
    int dataSize = 0;
    TaskData datas[tasksSize * 2];
    for (int i = 0; i < tasksSize; i++)
    {
        TaskData startData;
        TaskData endData;
        
        startData.taskId    = tasks[i].taskId;
        startData.timestamp = tasks[i].start;
        startData.op        = start;

        endData.taskId    = tasks[i].taskId;
        endData.timestamp = tasks[i].end;
        endData.op        = end;

        datas[dataSize++] = startData;
        datas[dataSize++] = endData;
    }
    
    // 根据时间排序
    quickSort(datas, 0, dataSize - 1);
    
    int activeTasks = 0;
    int maxTasks = 0;
    for (int i = 0; i < dataSize; i++)
    {
        if (datas[i].op == start)  // 「开启」一个任务,添加
        {
            activeTasks += 1;
        }
        else    // 「结束」一个任务,减少
        {
            activeTasks -= 1;
        }
        if (i == dataSize - 1 || datas[i].timestamp != datas[i + 1].timestamp)    // 「最后」一个任务 或 下一个的「时间」不相同,则任务数属于当前时间
        {
            maxTasks = max(activeTasks, maxTasks);
        }
    }
    
    return maxTasks;
}

int main(int argc, const char * argv[]) {
    
    TaskInfo tasks[10] = {
        {0, 0, 3},
        {1, 1, 2},
        {2, 1, 3},
        {3, 4, 5},
        {4, 6, 7},
        {5, 8, 9},
        {6, 10, 15},
        {7, 10, 17},
        {8, 11, 19},
        {9, 22, 23}};
    int ret = maxTaskCount(tasks, 10);
    printf("ret = %d\n", ret);
    
    return 0;
}

设任务的数量为 nn,任务的发起时间和结束时间放在一个 vector\texttt{vector} 里面,例如 vector<pair<int, int>> tasks\texttt{vector<pair<int, int>> tasks};那么实际上并发请求的任务数量只会在某个任务的「发起时间」或者「结束时间」产生变化。

所以我们只需要把每个任务的发起时间和结束时间放在一起排个序,比如设计一个 struct\texttt{struct},包含三个元素 (timestamp,task_id,op)(\texttt{timestamp}, \texttt{task\_id}, \texttt{op}),表示在 timestamp\texttt{timestamp} 的时间点,task_id\texttt{task\_id} 编号的任务产生了 op\texttt{op} 的变化(op=0\texttt{op}=0 表示其发起,op=1\texttt{op}=1 表示其结束)。我们按照 timestamp\texttt{timestamp} 升序排序,随后遍历排序的结果,就可以计算出每一个 timestamp\texttt{timestamp} 时并发的任务数量了。

input = n, tasks
L = list()

for index, (start_time, end_time) in enumerate(tasks)
    L.add((start_time, index, 0))
    L.add((end_time, index, 1))
end for

L.sort(key=timestamp)

active_tasks = 0

for (timestamp, task_id, op) in L:
    if op == 0 then active_tasks += 1 else active_tasks -= 1
    if (it is the last element in L) or timestamp != (the timestamp of the next element in L) then
        we know at at timestamp `timestamp`, there are `active_tasks` number of active tasks
    end if
end for

result the answer