car rental kotlin 3, Kotlin

Language: Layout:

//Kotlin 1.1

typealias Intervals = List<Pair<Int,Int>>

fun solve(pairs : Intervals) : Intervals {
  return best(pairs.sortedBy { it.first }, 0)
}

// find optimal set of intervals among pairs[i..]
fun best( pairs: Intervals, i: Int): Intervals {
  if (i >= pairs.count()) {
    return listOf()
  } else if (i == pairs.count()-1) {
    return listOf( pairs[i] )
  } else if (pairs[i].second < pairs[i+1].first) {
    // no overlap between pairs[i] and pairs[i+1]
    return best(pairs, i+1).plus( pairs[i] )
  } else {
    // find next interval which does not overlap with pairs[i]
    var j = i+2
    while (j < pairs.count() && pairs[j].first <= pairs[i].second) {
      j++
    }
    val a = best(pairs, j).plus( pairs[i] ) // use pairs[i] but not pairs[i+1]
    val b = best(pairs, i+1)                // use pairs[i+1] but not pairs[i]
    if (a.count() >= b.count()) {
      return a
    } else {
      return b
    }
  }
}

fun main(args: Array<String>) {
    val dayBegin = listOf(1, 40, 80, 41, 43, 81, 83)
    val dayEnd   = listOf(2, 50, 90, 42, 44, 82, 84)
    println (solve( dayBegin.zip(dayEnd) ) )
}

Show compiler warnings [ + ] Show input
Absolute running time: 0.62 sec, cpu time: 0.57 sec, memory peak: 23 Mb, absolute service time: 7,32 sec