Here’s the solution to both problems:
Question 1: Activity Selection Problem (Greedy Technique)
Approach:
1. Sort activities by their finish time: This ensures that you always consider the earliest
finishing activity first.
2. Select activities greedily: Start with the first activity (after sorting), and for each
subsequent activity, check if its start time is greater than or equal to the finish time
of the last selected activity. If yes, select it.
Code (Python):
def activity_selection(activities):
# Sort activities based on finish time
activities.sort(key=lambda x: x[1])
# Select the first activity
selected = [activities[0]]
last_finish = activities[0][1]
# Iterate through the remaining activities
for i in range(1, len(activities)):
if activities[i][0] >= last_finish:
selected.append(activities[i])
last_finish = activities[i][1]
return len(selected), selected
# Input
activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7), (8, 9)]
# Output
max_activities, selected_activities = activity_selection(activities)
print("Maximum number of activities:", max_activities)
print("Selected activities:", selected_activities)
Output:
Maximum number of activities: 4
Selected activities: [(1, 3), (4, 6), (6, 8), (8, 9)]
Question 2: Closest Pair of Points (Divide and Conquer)
Approach:
1. Divide the points into two halves based on their x-coordinates.
2. Conquer: Recursively find the closest pair of points in each half.
3. Combine: Check for a closer pair across the two halves within a strip of width 2 *
minimum distance.
4. Use a helper function to calculate the Euclidean distance between two points.
Code (Python):
import math
def distance(point1, point2):
return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)
def brute_force(points):
min_dist = float('inf')
closest_pair = None
n = len(points)
for i in range(n):
for j in range(i + 1, n):
dist = distance(points[i], points[j])
if dist < min_dist:
min_dist = dist
closest_pair = (points[i], points[j])
return closest_pair, min_dist
def closest_in_strip(strip, d):
min_dist = d
closest_pair = None
strip.sort(key=lambda point: point[1]) # Sort by y-coordinates
for i in range(len(strip)):
for j in range(i + 1, len(strip)):
if (strip[j][1] - strip[i][1]) >= min_dist:
break
dist = distance(strip[i], strip[j])
if dist < min_dist:
min_dist = dist
closest_pair = (strip[i], strip[j])
return closest_pair, min_dist
def closest_pair_recursive(points):
n = len(points)
if n <= 3:
return brute_force(points)
mid = n // 2
mid_point = points[mid]
left_closest, left_min = closest_pair_recursive(points[:mid])
right_closest, right_min = closest_pair_recursive(points[mid:])
d = min(left_min, right_min)
closest_pair = left_closest if left_min < right_min else right_closest
# Points in the strip
strip = [point for point in points if abs(point[0] - mid_point[0]) < d]
strip_closest, strip_min = closest_in_strip(strip, d)
if strip_min < d:
closest_pair = strip_closest
d = strip_min
return closest_pair, d
def closest_pair(points):
points.sort() # Sort points by x-coordinate
return closest_pair_recursive(points)
# Input
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
# Output
closest_pair_points, min_distance = closest_pair(points)
print("Closest pair of points:", closest_pair_points)
print("Distance:", min_distance)
Output:
Closest pair of points: ((2, 3), (3, 4))
Distance: 1.4142135623730951
