# 1. Course Overview, Interval Scheduling | Summary and Q&A

575.1K views
March 4, 2016
by
MIT OpenCourseWare
1. Course Overview, Interval Scheduling

## TL;DR

The earliest finish time selection rule is proven to be optimal for interval scheduling, but fails for weighted interval scheduling.

## Key Insights

• 🏋️ The earliest finish time selection rule is optimal for interval scheduling, but not for weighted interval scheduling.
• ❓ Weighted interval scheduling requires dynamic programming to find the optimal solution.
• 🎰 Non-identical machines in interval scheduling make the problem NP-complete.

## Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. SRINIVAS DEVADAS: So welcome to 6046. My name is Srinivas ... Read More

### Q: What is the TLDR summary of the content?

The earliest finish time selection rule is proven to be optimal for interval scheduling, but fails for weighted interval scheduling.

### Q: What is the main difference between interval scheduling and weighted interval scheduling?

Weighted interval scheduling assigns weights to requests and the goal is to schedule a subset of requests with maximum weight.

### Q: What is the complexity of the weighted interval scheduling dynamic programming solution?

The complexity is O(n^2), where n is the number of requests.

### Q: What happens if there are multiple non-identical machines in interval scheduling?

The problem becomes NP-complete, and a different approach is needed.

### Q: How can intractability be dealt with in interval scheduling?

Intractability can be managed by using polynomial-time algorithms that may not always provide the optimal solution, but are efficient for common cases.

## Summary & Key Takeaways

• The greedy algorithm with the earliest finish time is optimal for interval scheduling, but not for weighted interval scheduling.

• Weighted interval scheduling requires the use of dynamic programming to find the optimal solution.

• A small change to the interval scheduling problem, such as adding multiple non-identical machines, makes the problem NP-complete.