草庐IT

java - 查找包含给定时刻的间隔

coder 2024-03-30 原文

我正在尝试解决以下问题:给定 N 个时间间隔，每个时间间隔指定为(开始，结束)，不重叠，根据开始排序 - 找到包含给定日期的间隔。例如给出:

[1,4] [5,8] [9,10][11,20]

3 属于第一个间隔，15 属于第四个间隔等

到目前为止，我有以下基本想法:

  1. 我们可以使用二进制搜索找到对应的区间(Log N)
  2. 由于可能只有少数间隔较大，而其余间隔较小，因此根据持续时间对迭代进行排序可能是值得的。然后，在统计上，大多数时候我们会“命中”最长的间隔 (O(1))，只是有时这会导致 N 的最坏情况复杂度。

我在考虑是否可以将这两种方法结合起来。另一个想法是根据持续时间排序并将所有间隔插入树中，并按开始日期进行比较，这在最坏情况下最长持续时间按时间顺序排列时，这种方法的性能等于 2。

我想象的理想解决方案是有一棵树(或一些类似的数据结构)在顶部包含最长的间隔，然后两个分支将有接下来的两个最长的间隔等。但是，我看不出办法在那棵树中分支，即因为我们明确假设我们根据长度插入，所以我们不能真正丢弃树的左侧或右侧。

如有任何意见，我们将不胜感激。

最佳答案

这两种方法的简单组合在大多数情况下提供了 O(1)，在最坏的情况下提供了 O(logN)，但是大 O 中的隐藏常量符号将是双重的:

  1. 让原数组为intervals
  2. 创建第二个数组，按照建议的间隔长度降序排列。让它成为长度
  3. 对于每个查询，使用二进制搜索在 intervals 中搜索，并使用线性搜索在 lengths 中搜索。搜索将并行1 完成，第一个完成的搜索也会导致另一个停止。

因为在第 3 步中，我们可能会在 intervals 中执行最多 c*log(n) 步的二分查找，我们将最多执行 2* c*log(n) 总体步骤。如果我们在 lengths 中更快地找到元素，它会导致二分查找在中间结束，并且我们会减少操作次数(但使用 double 常量然后是原始方法)。

(1)不需要并行计算机，一步一步搜索，模拟单线程并行计算，直到找到答案。 (一般信息，理解答案不需要:S.Even、A.Itai 和 A.Shamir 在他们的文章 On the Complexity of TimeTable and Multi Commodity Flow Problems 中介绍了“并行搜索”的概念)

关于java - 查找包含给定时刻的间隔，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14019544/

给定javacodesectionalgorithmtreeintervals

有关java - 查找包含给定时刻的间隔的更多相关文章

  1. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  2. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  5. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  6. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  7. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  8. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  9. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  10. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐