最少在线禁止登录算法

Question

下面是经常性的每月帐单清单。第一个数字是账单到达的当月的哪一天（第一次付款的机会），第二个数字是当月的到期日（最后一次付款的机会）。你知道吗

• 16，1号
• 2，16岁
• 10、25岁
• 31、26岁
• 15、31岁

到达日期和到期日期之间的差值总是小于一个月。我正在寻找一种算法，对于任何数量的账单，无论其接收日期和到期日期如何，都将：

1. 制作一份清单，列出支付账单的网上银行的最少登录日期。你知道吗
2. 保证不会错过任何到期日。你知道吗

到目前为止，我的想法是寻找一个单一的日期（或日期范围），其中尽可能多的票据在到达日期和到期日期之间，然后重复这个过程，直到列表为空。你知道吗

这是最好的方法吗？有解决这个问题的现有算法吗？它叫什么？如果有代码示例，最好使用Python、PHP或伪代码。你知道吗

Answer 1

解决方案爪哇语：你知道吗

public class Ress {

    Set<Interval> intervals = new HashSet<>();

    public static void main(String[] args) {

        String[] input = {"16 1","2 16","10 25","31 26","15 31"};
        System.out.println(minimumLogins(input));

    }

    public static int minimumLogins(String[] input) {
        Ress r = new Ress();
        for (String s : input) {
            Scanner sc = new Scanner(s);
            Bill b = new Bill(sc.nextInt(), sc.nextInt());
            r.addToIntervals(b);
        }
        //If we have to print the dates on which to pay the bills, then it will be any date inside the different intervals.
        return r.intervals.size();
    }

    public void addToIntervals (Bill b) {
        Interval i = null;
        for(Interval in:intervals){
            if(in.canAddBill(b)) {
                i = in;
                break;
            }
        }
        if(i==null) {
            i = new Interval(b);
            intervals.add(i);
        }
        i.addBill(b);
    }

}

class Bill{
    int receiveDate;
    int dueDate;

    public Bill(int a, int b) {
        receiveDate = a;
        if(b<a) {
            // adding to represent the date in next month
            b += 31;
        }
        dueDate = b;
    }
}

class Interval{
    int startDate;;
    int endDate;
    List<Bill> bills;

    public Interval(Bill b) {
        startDate = b.receiveDate;
        endDate = b.dueDate;
        bills = new ArrayList<>();
    }

    public void addBill(Bill b) {
        bills.add(b);
        //Reset interval boundaries based on the newly added bill
        if(b.dueDate<this.endDate) {
            endDate = b.dueDate;
        }
        if(b.receiveDate>this.startDate) {
            startDate = b.receiveDate;
        }
    }

    public boolean canAddBill(Bill b) {
        /*
         * Bill can be added if it lies in the interval.
         */
        if(b.dueDate<=this.endDate || b.receiveDate<=this.endDate) {
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + endDate;
        result = prime * result + startDate;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Interval other = (Interval) obj;
        if (endDate != other.endDate)
            return false;
        if (startDate != other.startDate)
            return false;
        return true;
    }
}

Answer 2

上述代码将仅对以下提到的输入返回答案2：

1. 1->3 (Bill A)
2. 3->6 (Bill B)
3. 6->9 (Bill C)
4. 9->10 (Bill D)

解释如下： 1我们得到的第一个输入帐单为1->；3。 2这项法案被加入到它的第一套：与周期：1->；3。 三。下一个账单是3->；6，它与1->；3是同一时期 票据的收票日期与票据的结束期间相同。你知道吗

set1:(1->3) { BillA, BillB}

1. 下一个账单是6->；9，这将创建一个新的账单集：

   集合1:（1->；3）{BillA，BillB} 集合2:（6->；9）{BillC}。

2. 下一个传入帐单是9->；10，由于与上面相同的原因，它只会再次进入第2组。你知道吗

   集合1:（1->；3）{BillA，BillB} 集合2:（6->；9）{BillC，BillD}

我相信这是正确的解决方案，因为问题真的要求我们只识别不相交集的数量。你知道吗

Answer 3

实际上，您的解决方案不正确，原因如下：

假设你有许多天有相同数量的范围相交，这个数量是所有其他时间中最大的。例如：

1. 1->；3个
2. 3-大于6
3. 6-大于9
4. 9-大于10

据我所知，在接下来的几天里（3、6、9），他们都有两张账单需要支付，其他日子都没有更多的账单需要支付。现在，由于您不可能确定从哪一天开始，您可以选择第6天并支付账单（2，3）。接下来，您别无选择，只能选择第3天和第9天来支付相应的账单。您使用了3天，而答案是2选择第一天3同时支付1和2账单，然后选择第9天3和4账单。你知道吗

不管怎样，我很肯定我有一个几乎线性的时间解决方案给你。你知道吗

首先，让我们把您的输入弄清楚一点，如果第二个数字实际上比第一个小，那么在第二个数字后面加上30（或者在每月31天的情况下加上31）。您的示例如下所示：

• 16->；31

• 2->；16

• 10->；25

• 31->；56

• 15->；31

我的想法基于以下两个事实：

1. 无论何时登录，最好是支付所有可用但尚未支付的账单。

2. 当遍历从开始（第1天）到结束（第60天）的一个月的时间线时，如果可能，最好尝试延迟日志记录过程；也就是说，如果延迟不会导致任何到期日被错过。

为此，我们首先为每个条目分配一个唯一的ID：

1. 16->；31

2. 2->；16

3. 10->；25

4. 31->；56

5. 15->；31

让我们使用扫描线算法，它通常解决与区间相关的问题。创建一个名为扫描的向量，其中该向量的每个元素都包含以下信息：

• ID：对应条目的ID。

• 计时器：指示第一天或最后一天付账。

• 键入：只是一个标志。0表示Timer包含第一天支付账单编号ID（第一个编号），而1表示Timer包含最后一天支付账单编号ID（第二个编号）。

对于每个条目，将2个元素插入到扫描向量：

1. ID=条目的ID，计时器=第一个数字，类型=0。

2. ID=条目的ID，计时器=第二个数字，类型=1。

将所有这些元素插入扫描向量后，其大小将等于2x条目数。根据Timer的值对该向量进行递增排序，如果是平局，则根据Type的值进行递增排序（以便在条目结束之前首先检查条目的开始）。你知道吗

遍历扫描向量，同时保留一个包含到目前为止所有未付账单的id的集合，我们称这个集合为就绪。在每一步中，你可能会遇到以下一个问题ng元素（基于我们添加的类型）：

• 类型=0。在这种情况下，这意味着您已经到了第一次能够支付账单编号ID的日期。还不付帐。相反，将其ID插入我们的Ready集合（想法2）。

• 类型=1。在这种情况下，检查相应的ID是否在Ready集合内。如果不是，就继续下一个元素。如果它实际上在准备好的集合中，这意味着您已经到了支付以前未付账单的最后一天。你别无选择，只能支付这张账单，以及当天设置的就绪的内的所有其他账单（想法1）。通过支付账单，我的意思是将包含您答案的变量增加1，如果对您很重要，请将Ready设置并存储在某个地方，所有这些ID必须在当天支付。完成此操作后，您已经支付了所有已准备好的账单，只需清除已准备好的（清除其中的所有元素）。

每个条目导致2个元素插入到扫描向量中，并且每个条目将恰好插入到就绪集合中一次，并删除一次。检查ID内部Ready集合的成本是O（logn），并且每个条目只检查一次。排序操作是O（N logn）。因此，您的总复杂性将是：O（N logn）其中N是您拥有的条目总数。你知道吗

Python不是真正的我最强的编程语言，所以我将把上面提到的算法编码的任务留给你（C++中，例如，它并不难实现）。希望有帮助！你知道吗

---

编辑（感谢@Jeff的评论）

您可以使用以下方法使您的解为偶数O（N）：

您可以迭代从1到60的天数，而不是迭代事件，并保持与我提到的相同的处理方法。这样我们消除了排序操作。你知道吗

要从插入和检查操作中删除O（logn）因子，我们可以使用@Jeff的注释中提到的哈希表，或者使用布尔数组Visited，带有向量Ready。您将在向量中插入就绪票据。当您需要支付账单时，只需迭代就绪向量，并在已访问数组中相应的索引中将其中的账单标记为已访问。只需访问Visited数组中的相应索引即可检查I bill是否已支付。你知道吗

有趣的是，在写了我的答案之后，我想出了几乎和@Jeff评论中提到的完全相同的优化。然而，由于时间有限，我决定不把答案弄得太复杂，让它更容易理解。既然@Jeff提到了优化，我决定把它也添加到我的答案中。但是，请注意，通过此优化，总体复杂度现在等于O（N+D），其中N是账单总数，D是总天数。因此，如果D很大，实际上需要使用第一个解决方案。你知道吗