In loss minimization scheduling, we are given a set of jobs (with costs), and the goal is to remove the smallest (cheapest) subset of jobs so that the remaining jobs can be feasibly scheduled. In the case where all jobs are simple intervals of execution time, loss minimization scheduling is classically known to be linear-time solvable. We examine some generalizations of this case which are NP-hard to solve optimally, and present efficient approximation algorithms for these generalizations.