jjzjj

php - 查找多个间隔之间的最长间隔

coder 2024-04-18 原文

假设您有一个变量 $n 表示时间轴上的多个分区，以及一个可变长度的间隔数组:

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10],
];

问题是在时间轴上找到这些间隔之间的最大差距。对于上面的问题，我们有两个长度为 2 和 1 的间隙，所以答案应该是 2。为了更好地形象化它:

我直接的方法效率不高......

  1. 初始化一个长度为 $n 的空时间轴数组，每个元素都设置为“E”，如空。
  2. 在每个间隔上进行 Foreach 循环，并创建另一个从间隔开始到间隔结束的 for 循环，并将时间轴数组中的这些元素设置为拍摄时的“T”。
  3. 遍历时间线数组并启动一个 $counter，它随着每个连续的“E”字符递增，如果它的值大于前一个，则将其保存到变量 $max。

我可以做哪些改进？

请注意:

  • 区间总是根据它们的起始位置排序。
  • 间隔不必从时间轴的开头开始，也不必在时间轴的末尾结束。因此，第一个间隔之前可能有一个间隙，最后一个间隔之后可能有一个间隙。
  • 间隔可以重叠。所以简单地计算下一个间隔的开始减去这个间隔的结束是行不通的......考虑这个例子:[1,5] [2,4] [6,10] [6,8]

最佳答案 

<?php

$n = 10;
$intervals = [
  [1, 2],
  [2, 2],
  [5, 6],
  [8, 10]
];

$non_overlapping = [];
$start = -1;
$end = -1;

foreach($intervals as $index => $interval){
    if($start == -1) $start = $interval[0];
    if($end == -1) $end = $interval[1];

    if($index == 0) continue; // since it's first index

    if($interval[0] >= $end){
        $non_overlapping[] = [$start,$end];
        $start = $interval[0];
        $end = $interval[1];
    }else{
        $end = max($end,$interval[1]);
    }
}

$non_overlapping[] = [$start,$end];
$maximum_gap = 0;
$prev_end = 0;

foreach($non_overlapping as $index => $interval){
    $maximum_gap = max($maximum_gap,$interval[0] - $prev_end - 1);
    $prev_end = $interval[1];
}

$maximum_gap = max($maximum_gap,$n - $prev_end);

echo $maximum_gap;
  • 由于您的间隔是根据开始时间排序的，我们制作了一个新的非重叠间隔数组。
  • 现在，我们只需用之前的结束时间减去新的开始时间，最后用 $n 本身减去最后的结束时间，并找到最大差距。

关于php - 查找多个间隔之间的最长间隔，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56722946/

php间隔intervalsectionmaximum_gaparraysalgorithmlogic

有关php - 查找多个间隔之间的最长间隔的更多相关文章

  1. ruby-on-rails - Rails 3 中的多个路由文件 - 2

    Rails2.3可以选择随时使用RouteSet#add_configuration_file添加更多路由。是否可以在Rails3项目中做同样的事情？ 最佳答案 在config/application.rb中:config.paths.config.routes在Rails3.2(也可能是Rails3.1)中，使用:config.paths["config/routes"] 关于ruby-on-rails-Rails3中的多个路由文件，我们在StackOverflow上找到一个类似的问题

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

    我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

  4. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  5. ruby - 多个属性的 update_column 方法 - 2

    我有一个具有一些属性的模型:attr1、attr2和attr3。我需要在不执行回调和验证的情况下更新此属性。我找到了update_column方法，但我想同时更新三个属性。我需要这样的东西:update_columns({attr1:val1,attr2:val2,attr3:val3})代替update_column(attr1,val1)update_column(attr2,val2)update_column(attr3,val3) 最佳答案 您可以使用update_columns(attr1:val1,attr2:val2

  6. ruby-on-rails - 在 ruby​​ .gemspec 文件中，如何指定依赖项的多个版本？ - 2

    我正在尝试修改当前依赖于定义为activeresource的gem:s.add_dependency"activeresource","~>3.0"为了让gem与Rails4一起工作，我需要扩展依赖关系以与activeresource的版本3或4一起工作。我不想简单地添加以下内容，因为它可能会在以后引起问题:s.add_dependency"activeresource",">=3.0"有没有办法指定可接受版本的列表？~>3.0还是~>4.0？ 最佳答案 根据thedocumentation,如果你想要3到4之间的所有版本，你可以这

  7. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

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

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

  9. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  10. 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

随机推荐