#### Discuss some real world problems, to which the techniques given below are applicable

(i) Divide & Conquer

(ii) Dynamic Programming

(iii) Greedy Approach

**Interval scheduling**is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an

*interval*describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is

*compatible*if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

The

*interval scheduling maximization problem*(ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.
## 0 comments:

## Post a Comment