Activity Selection Problem in DSA C - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with multiple activities. Each activity has a start time and an end time. You want to select the maximum number of activities that don't overlap so attendees can participate in as many as possible.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities from a given list using the Activity Selection Problem approach.

📋 What You'll Learn

Create two arrays called start and end with exact values for activity start and end times

Create an integer variable n to hold the number of activities

Implement the activity selection logic using a for loop and select activities based on their end times

Print the count of the selected activities

💡 Why This Matters

🌍 Real World

Scheduling meetings, conference talks, or any events where time slots must not overlap to maximize participation.

💼 Career

Understanding greedy algorithms and scheduling problems is important for software engineers working on calendar apps, resource allocation, and optimization tasks.

1

Create activity start and end time arrays

Create two integer arrays called start and end with these exact values: start = {1, 3, 0, 5, 8, 5} and end = {2, 4, 6, 7, 9, 9}. Also create an integer variable n and set it to 6.

DSA C

# Your code here

Hint

Use arrays to store start and end times exactly as given. Also create an integer n for the number of activities.

2

Initialize variables for activity selection

Create an integer variable called count and set it to 1. Create an integer variable called last_selected and set it to 0 to track the last selected activity index.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
# Your code here

Hint

Initialize count to 1 because the first activity is always selected. last_selected keeps track of the index of the last chosen activity.

3

Select maximum activities using a loop

Use a for loop with an integer variable i starting from 1 to n - 1. Inside the loop, check if start[i] is greater than or equal to end[last_selected]. If yes, increment count by 1 and update last_selected to i.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
int count = 1;
int last_selected = 0;
// Your code here

Hint

Loop through activities starting from the second one. Select an activity if its start time is after or equal to the last selected activity's end time.

4

Print the count of selected activities

Use printf to print the value of count followed by a newline.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
int count = 1;
int last_selected = 0;
for (int i = 1; i = end[last_selected]) {
        count++;
        last_selected = i;
    }
}
// Your code here

Hint

Print the total number of selected activities using printf.