在同一时期，这座城市的最大人数是多少？
在同一时期，这座城市的最大人数是多少？
提问于 2019-09-11 07:17:45
今天在班上讨论过的一个问题是:N个巴黎是给定的(ai，bi)，每一对代表一个人，ai，bi代表他2019年的进出城日期。问题是，在同一时期，这座城市的最大人数是多少。
我尝试将日期转换为1,365，并将它们插入到一个AVL的入口和另一个AVL的退出日期中，并保存它们在遍历一棵树时的指针，并在需要时更新最大值。我相信这是一个幼稚的灵魂，因为它需要O(n^2)。
我们学习的数据结构有:数组、链表、队列、堆栈、堆、BST、AVL、堆、哈希表、SkipList和图。
回答 1
Stack Overflow用户
发布于 2019-09-11 12:00:15
您可以使用array来执行此逻辑。
由于一年中的天数是固定的，因此需要创建一个数组来记录该市在该特定一天的人数。
count[365] = {0}; //Reset the counter, all entries should be zero.
maxCount = 0;
maxDay = -1;
for(day from 0 to (365-1))
{
for(i from 0 to (n-1) person)
{
if(day >= ai && day <= bi) //Update this check based on whether ai and bi are inclusive or not.
{
count[day] = count[day]+1;
if(count[day] > maxCount) //Keep track of maxCount, if required update it.
{
maxCount = count[day];
maxDay = day;
}
}
}
}
Output maxDay, maxCount;上述逻辑的时间复杂度为O(365*n) => O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57879258
复制相关文章
相似问题
腾讯云开发者
