object model {
type MovieId = Long
type UserId = Long
case class View(userId: UserId, movieId: MovieId)
}
import model._
object Solution extends App {
def diverseMovies(views: Seq[View], numMovie: Int): Set[MovieId] = {
def choose(except: Set[UserId] = Set.empty): MovieId = {
views.collect { case view if !except(view.userId) => view }.
groupBy(_.movieId).mapValues(_.size).maxBy(_._2)._1
}
def viewersOf(movie: MovieId) =
views.filter(_.movieId equals movie).map(_.userId).toSet
val result: (List[MovieId], Set[UserId]) =
((List.empty[MovieId], Set.empty[UserId])/:(1 to numMovie)) ({
case ((movies: List[MovieId], ignoredUsers: Set[MovieId]), _) => {
val movie = choose(ignoredUsers)
(movie::movies, ignoredUsers ++ viewersOf(movie))
}
})
result._1.toSet
}
}
