Question 1: Remove overlapping sets
You are given n variable length sets with each set like set1: [s1.....e1], set2:[s2.....e2] with the condition that the sets overlap (i.e. if you represent them on number line, they intersect). Now you have to remove the minimum number of sets from here so that the remaining sets are disjoint.
For example you have set S1, S2, S3 with S1 and S3 disjoint and S2 overlapping both S1 and S3 then we remove S2 to get the answer.
Strategy:
Assume all the sets are sorted.
Find the maximum value out of all the sets i.e., compare the last value in each set & find the maximum value.
Create a bitset with a size that of this maximum value.
Walk through the first set & for each value set the corresponding bit. i.e, if s1 = 6, then the 6th bit is set.
Pick the next set. Walk through it. If you find any bit is already set, for any value of this set, then that set needs to be removed.
Follow the same for all the remaining sets.
Question 2: Merge Overlapping Intervals
Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity.
For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1, 4}. Similarly {5, 7} and {6, 8} should be merged and become {5, 8}
Strategy:
1. Sort the intervals based on increasing order of
starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
a. If the current interval does not overlap with the stack
top, push it.
b. If the current interval overlaps with stack top and ending
time of current interval is more than that of stack top,
update stack top with the ending time of current interval.
4. At the end stack contains the merged intervals.
http://www.geeksforgeeks.org/merging-intervals/
You are given n variable length sets with each set like set1: [s1.....e1], set2:[s2.....e2] with the condition that the sets overlap (i.e. if you represent them on number line, they intersect). Now you have to remove the minimum number of sets from here so that the remaining sets are disjoint.
For example you have set S1, S2, S3 with S1 and S3 disjoint and S2 overlapping both S1 and S3 then we remove S2 to get the answer.
Strategy:
Assume all the sets are sorted.
Find the maximum value out of all the sets i.e., compare the last value in each set & find the maximum value.
Create a bitset with a size that of this maximum value.
Walk through the first set & for each value set the corresponding bit. i.e, if s1 = 6, then the 6th bit is set.
Pick the next set. Walk through it. If you find any bit is already set, for any value of this set, then that set needs to be removed.
Follow the same for all the remaining sets.
Question 2: Merge Overlapping Intervals
Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity.
For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1, 4}. Similarly {5, 7} and {6, 8} should be merged and become {5, 8}
Strategy:
1. Sort the intervals based on increasing order of
starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
a. If the current interval does not overlap with the stack
top, push it.
b. If the current interval overlaps with stack top and ending
time of current interval is more than that of stack top,
update stack top with the ending time of current interval.
4. At the end stack contains the merged intervals.
http://www.geeksforgeeks.org/merging-intervals/
No comments:
Post a Comment