我正在尝试解决此问题：https://open.kattis.com/problems/workstations

  

Penelope是新建超级计算机管理团队的一部分。   她的工作是为来到这里的研究人员分配工作站。   在超级计算机上运行他们的计算。佩内洛普（Penelope）非常懒惰，   讨厌为即将到来的研究人员解锁机器。她可以解锁   机器从她的桌子远程，但不觉得这   艰巨的任务符合她的资格。她是否应该决定忽略   她可以简单地要求研究人员不要使用的安全准则   他们离开时锁定他们的工作站，然后分配新的   研究人员到不再使用的工作站   仍然解锁。这样，她只需要解锁每个工作站   对于第一个使用它的研究人员，这将是一个巨大的进步   佩内洛普（Penelope）。

     

不幸的是，如果出现以下情况，未使用的工作站会自动锁定自己：   它们闲置了超过?分钟。工作站安装完后   锁定了自己，佩内洛普（Penelope）必须为下一个研究人员再次将其解锁   使用它。给定确切的到达和离开时间表   研究人员，你能告诉佩内洛普她可以通过保存多少次解锁   要求研究人员离开时不要锁定工作站   并以最佳方式将即将到来的研究人员分配给工作站？   您可能会假设总是有足够的工作站。

（请参阅链接，其中包含示例，格式更好）。

我的方法是贪婪算法。

我首先按结束时间排序。

我反复记录给定工作时间的结束时间。对于新工作时间，我找到了最接近的工作站，其结束时间小于此新工作时间的开始时间。如果没有，则无法利用解锁。

代码：

import java.util.*
import kotlin.math.max

private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single int

private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs



fun greedy(times: List<Pair<Long,Long>>,m: Long): Long {
    val sortedTimes = times.sortedBy { it.second }
    val counter = mutableMapOf<Long,Long>()
    val treeSet = TreeSet<Long>()
    var count: Long = 0
    for (i in 0 until sortedTimes.size) {
        val currentStart = sortedTimes[i].first
        val prev = treeSet.lower(currentStart + 1)
        if (prev != null && prev + m >= currentStart) {
            counter[prev] = counter[prev]!! - 1
            if (counter[prev]!! == 0.toLong()) {
                treeSet.remove(prev)
            }
            count += 1
        }
        counter.putIfAbsent(sortedTimes[i].second,0)
        counter[sortedTimes[i].second] = counter[sortedTimes[i].second]!! + 1
        treeSet.add(sortedTimes[i].second)
    }
    return count
}

fun main(args: Array<String>) {
    val (n,m) = readLongs()
    val times = mutableListOf<Pair<Long,Long>>()
    for (i in 0 until n) {
        val (start,extra) = readLongs()
        val end = start + extra
        times.add(Pair(start,end))
    }
    val ans = greedy(times,m)
    println(ans)
}

这通过了示例，但在某些隐藏的测试用例上失败了。

我很喜欢如何改进算法的一些建议。