Instructions:

Typically, the clearest way to explain an algorithm is in English, with the use of some notation. A clear explanation followed by annotated pseudo-code is also fine.

Remember that when a problem asks you to design an algorithm, you must also prove the algorithms correctness and analyze its running time, i.e., the running time must be bounded by a polynomial function of the input size. (Include Proof)

(3) (10 points) You are helping a group of students find homework partners. The plan is to have pairs of students spend some time t each week working together. We will assume that you have n students, and every student prefers to work in a pair, if possible. To facilitate the process of organizing these pairs, you've asked each student i to specify a single time interval Ii=[si,fi] that available to them every week. We call a pair (i,j) of two students an eligible pair if their intervals of time overlap by at least t. Give an algorithm that selects as many eligible pairs as possible such that every paired student is part of at most one of the selected pairs, and runs in time at most O(n2)