Algorithms, please help! 2. Let X be a set of n intervals on the real line. A su

Question

Algorithms, please help!

2. Let X be a set of n intervals on the real line. A subset of intervals Y C X is called a tiling path if the intervals in Y cover the intervals in X, that is, any real value that is contained in some interval in X is also contained in some interval in Y. The size of a tiling cover is just the number of intervals Describe and analyze an algorithm to compute the smallest tiling path of X as quickly as possible. Assume that your input consists of two arrays Xi[1,...,n] and XR1,., n] representing the left and right endpoints of the intervals in X. If you use a greedy algorithm, you must prove that it is correct. A set of intervals. The seven shaded intervals form a tiling path.

Explanation / Answer

Algorithm :

1. Sort the intervals by start time in ascending order

2. First interval will be part of tilling path.

3. Take this interval as current interval.

4. Now, from all intervals having end time greater than current interval end time, but having start time overlapping with current interval or interval with minimum start time which is not overlapping with current interval(in case there is no interval which is overlapping with current interval), select a interval having greatest end time. Add this interval to our tilling path, and set it this interval as current interval.

5. Repeat step 4, till all intervals are covered.

6. Number of intervals in tilling path is our answer.

Now, we have to prove that our approach will cover all intervals present in our original set.

Whenever we are adding interval to our tilling path, we are only considering intervals overlapping with last added interval or interval with minimum start time for intervals which are not overlapping. Thereby we are ensuring that no interval is missed while generating a tilling path.

Now, we have to prove that our approach will generate a tilling path having smallet number of intervals contained in it.

Let say tilling path returned by our greedy algorithm is {g1,g2,g3,.....gk}, Now let say some optimal schedule returns a tilling path {p1,p2,p3,...pm}, here m < k,

For this to be true, there must exist a interval pi which can replace gj and gj+1, for that to happend it must statisfy below condition

pi start time <= gj start time and pi end time >= gj+1 end time, If this is true than our algorithm would have picked pi from the set {pi, gj, gj+1} as pi has greatest end time. So, m is equal to k.

Hence our greedy algorithm always produces optimal schedule.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.