找到两次的"NOR“

Question

我有一个由两个数组组成的格式，表示时间段的开始和结束，即上午9点到下午5点，表示为：

int[] startTime = {9, 0};
int[] endTime = {17, 0};

这样做的目的是从这些元素的列表(保存在基本类中，格式是为了便于数据库输入)中找出没有元素占用的时间段(我想它可以称为NOR?)。例如，当提供09:00-14:00和16:00-17:00时(假设只有9am-5 5pm之间的条目感兴趣)，它应该返回14:00-16:00。

该列表并不是特别大，尽管它很可能包含重复项并打乱顺序。在这一点上我不知道该怎么做，有什么想法吗？

需要澄清的是:一个时间列表正在与另一个时间列表进行比较(一个是本地的，另一个是从其他地方拉出来的)

Answer 1

步骤1:按(结束时间，开始时间)对间隔进行升序排序

步骤2:合并间隔if end_time(i) >= start_time(i+1)

此时，您就有了一个经过重复数据消除的、经过排序的非重叠间隔列表。

步骤3:输出全部(end_time(i)，start_time(i+1))

Answer 2

你能自己阅读Scala代码并将其翻译成Java吗？

case class Interval (lower: Int, upper: Int) {    
    def deflate () : List [Int] = {(lower to upper).toList}
}

def list2disjunctIntervals (li: List[Interval]) : List[Interval] = {
  val united = (li.flatMap (_.deflate).distinct).sorted

  def split (l: List [Int], sofar: List[Int]): List[List[Int]] = l match {
    case Nil => List (sofar)
    case h::t=> if (sofar.isEmpty) split (t, List (h)) else
      if (h == sofar.head + 1) split (t, h :: sofar)
      else sofar :: split (t, List (h))
  }

  val sublists = split (united, Nil)
  sublists.map (l => Interval (l.last, l.head))
}

演示：

val li = List (Interval (0, 4), Interval (7, 12), Interval (1, 3), Interval (5, 8), Interval (15, 17), Interval (16, 22))

scala> list2disjunctIntervals (li) 
res64: List[Interval] = List(Interval(0,12), Interval(15,22))

在prosa中: Interval是一个类，由它的边界定义。Deflate是(到目前为止)唯一的方法，它为一个区间生成该区间内的值：(9，12) => (9，10，11，12)

list2disjunctIntervals采用间隔列表。它有一个内部方法united，该方法压缩所有间隔，然后将值缩减为不同的值，并对它们进行排序。因此对于(3,4)(6,9)(9,11)，它产生(3,4,6,7,8,9,10,11)。

Split获取此列表，并将其分为多个列表：(3，4)和(6，...11)。

最后一个调用是从子列表生成新的间隔。

Answer 3

下面是一个粗略的Java方法：

import java.util.*;

class Interval {

    int lower, upper;

    Interval (int l, int u) {
      lower = l;
      upper = u;
    }

    boolean isMergeable (Interval other) {
        return (upper >= other.lower && lower <= other.upper);
    }
    /**
        if a contains b fully, result is a
        if b contains a fully, result is b
        if a and b don't overlap result is (a, b)
        if a and b overlap, result is Interval min(a.lower, b.lower), max(a.upper, b.upper)
        i(10,12).merge (13, 17) fails
    */
    List <Interval> merge (Interval other) {
      List <Interval> li = new ArrayList <> ();
        if (lower < other.lower && upper > other.upper)
          li.add (this);
        else if (lower > other.lower && upper < other.upper)
          li.add (other);
        else if (upper < other.lower || lower > other.upper)
          {li.add (this); li.add (other);}
        else
          li.add (new Interval (Math.min (lower, other.lower), Math.max (upper, other.upper)));
        return li;
    }   

    // the usual, boring stuff from here    
    @Override
    public String toString ()
    {
          return "[" + lower + ":" + upper + "]";
    }

    // to make List<Interval>.contains(interval) work
    @Override public boolean equals (Object o) {
      if (! (o instanceof Interval))
        return false;
      Interval other = (Interval)o;
      return lower == other.lower && upper == other.upper;
    }

    @Override
    public int hashCode () {
      return 1023*upper + lower;
    }
}

和一个测试场景：

public class IntervalTest {

  static List <Interval> mergeList (List <Interval> li) {
    List <Interval> iset = new ArrayList <> ();
    for (Interval i1 : li) {
      Interval m = i1;
      for (Interval i2 : li)
        if (i2.isMergeable (m))
            m = i2.merge (m).get(0);
      if (! iset.contains (m))
          iset.add (m);
    }
    return iset;
  }

  public static void main (String[] args)
  {
    Interval[] ia = {new Interval (0, 4), new Interval (1, 2), new Interval (7, 12), new Interval (1, 3), new Interval (5, 8), new Interval (15, 17), new Interval (16, 19), new Interval (9, 13), new Interval (22, 23)};
    List<Interval> li = Arrays.asList (ia);
    System.out.println (li);
    System.out.println (mergeList (li));
  }
}

输出：

// atomic Intervals:
[[0:4], [1:2], [7:12], [1:3], [5:8], [15:17], [16:19], [9:13], [22:23]]
// merged:
[[0:4], [5:13], [15:19], [22:23]]

请注意，在日常生活中，人们对边界的理解是不同的，所以当我说我从1-3和4-5看电视时，3和4之间显然是有差距的。

但是，如果我说第一季度从1到3个月，第二季度从4个月到6个月，那么q1和q2之间没有差距，3个月和4个月之间也没有差距。给定的算法在4和5之间产生了差距，因此如果需要/首选的话，必须对此进行调整。

要查找打开的时隙，您必须对合并后的数组进行排序，并查找(如果有)第一个间隔之前、最后一个间隔之后以及两个间隔之间的时间。

但是，如果在您的用例中，开始时间0-9和17-24总是包含在列表中，那么您只需搜索间隔。