The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

In Activity-Selection problem, each activity $i$ has a start time $s_i$ and a finish time $f_i$ where $s_i \leq f_i$. Activities $i$ and $j$ are compatible if

- $s_i \geq f_j$
- $s_j \geq f_i$
- $s_i \geq f_j$ or $s_j \geq f_i$
- $s_i \geq f_j$ and $s_j \geq f_i$

0 votes

Answer is **C**

Two activities are **compatible **if they can be completed in some order and don't overlap in time. To complete two activities, **START** time of one activity must be greater than or equal to **FINISH** time of other activity i.e one activity must start only after other finishes. So,

**S _{i} >= F_{j} or S_{j} >= F_{i}**

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,765 answers

192,355 comments

90,817 users