Data Modelling & AI Data Structure & Algorithm

Activity selection problem with K persons

23 June 2025

0

Given two arrays S[] and E[] of size N denoting starting and closing time of the shops and an integer value K denoting the number of people, the task is to find out the maximum number of shops they can visit in total if they visit each shop optimally based on the following conditions:

A shop can be visited by only one person
A person cannot visit another shop if its timing collide with it

Examples:

Input: S[] = {1, 8, 3, 2, 6}, E[] = {5, 10, 6, 5, 9}, K = 2
Output: 4
Explanation: One possible solution can be that first person visits the 1st and 5th shops meanwhile second person will visit 4th and 2nd shops.

Input: S[] = {1, 2, 3}, E[] = {3, 4, 5}, K = 2
Output: 3
Explanation: One possible solution can be that first person visits the 1st and 3rd shops meanwhile second person will visit 2nd shop.

Approach: This problem can be solved using the greedy technique called activity selection and sorting. In the activity selection problem, only one person performs the activity but here K persons are available for one activity. To manage the availability of one person a multiset is used.

Follow the steps below to solve the problem:

Initialize an array a[] of pairs and store the pair {S[i], E[i]} for each index i.
Sort the array a[] according to the ending time.
Initialize a multiset st to store the persons with ending time of shop they are currently visiting.
Initialize a variable ans with 0 to store the final result.
Traverse each pair of array a[],
1. If a person is available i.e a[i].first is greater than or equal to the ending time of any person in the multiset st, then increment the count by 1 and update the ending time of that element with new a[i].second.
2. Otherwise, continue checking the next pairs.
Finally, print the result as count.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Comparator
bool compareBy(const pair<int, int>& a,
               const pair<int, int>& b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}
// Function to find maximum shops
// that can be visited by K persons
int maximumShops(int* opening, int* closing,
                 int n, int k)
{
    // Store opening and closing
    // time of shops
    pair<int, int> a[n];
 
    for (int i = 0; i < n; i++) {
        a[i].first = opening[i];
        a[i].second = closing[i];
    }
 
    // Sort the pair of array
    sort(a, a + n, compareBy);
 
    // Stores the result
    int count = 0;
 
    // Stores current number of persons visiting
    // some shop with their ending time
    multiset<int> st;
 
    for (int i = 0; i < n; i++) {
 
        // Check if current shop can be
        // assigned to a person who's
        // already visiting any other shop
        bool flag = false;
 
        if (!st.empty()) {
 
            auto it = st.upper_bound(a[i].first);
 
            if (it != st.begin()) {
                it--;
 
                // Checks if there is any person whose
                // closing time <= current shop opening
                // time
                if (*it <= a[i].first) {
 
                    // Erase previous shop visited by the
                    // person satisfying the condition
                    st.erase(it);
 
                    // Insert new closing time of current
                    // shop for the person satisfying ?he
                    // condition
                    st.insert(a[i].second);
 
                    // Increment the count by one
                    count++;
 
                    flag = true;
                }
            }
        }
 
        // In case if no person have closing
        // time <= current shop opening time
        // but there are some persons left
        if (st.size() < k && flag == false) {
            st.insert(a[i].second);
            count++;
        }
    }
 
    // Finally print the ans
    return count;
}
 
// Driver Code
int main()
{
 
    // Given starting and ending time
    int S[] = { 1, 8, 3, 2, 6 };
    int E[] = { 5, 10, 6, 5, 9 };
 
    // Given K and N
    int K = 2, N = sizeof(S)
                   / sizeof(S[0]);
 
    // Function call
    cout << maximumShops(S, E, N, K) << endl;
}

Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;
 
class Main
{
  public static int maximumShops(int[] opening, int[] closing, int n, int k) 
  {
     
    // Store opening and closing time of shops
    Pair[] a = new Pair[n];
    for (int i = 0; i < n; i++) {
      a[i] = new Pair(opening[i], closing[i]);
    }
 
    // Sort the pair of array
    Arrays.sort(a, new Comparator<Pair>() {
      @Override
      public int compare(Pair a, Pair b) {
        if (a.second != b.second) {
          return a.second - b.second;
        }
        return a.first - b.first;
      }
    });
 
    // Stores the result
    int count = 0;
 
    // Stores current number of persons visiting
    // some shop with their ending time
    TreeSet<Integer> st = new TreeSet<>();
 
    for (int i = 0; i < n; i++) 
    {
       
      // Check if current shop can be assigned to
      // a person who's already visiting any other shop
      boolean flag = false;
 
      if (!st.isEmpty()) {
        Integer it = st.higher(a[i].first);
        if (it != null && it <= a[i].first) 
        {
           
          // Erase previous shop visited by 
          // the person satisfying the condition
          st.remove(it);
           
          // Insert new closing time of current shop 
          // for the person satisfying ?he condition
          st.add(a[i].second);
           
          // Increment the count by one
          count++;
          flag = true;
        }
      }
 
      // In case if no person have 
      // closing time <= current shop opening time
      // but there are some persons left
      if (st.size() < k && flag == false) {
        st.add(a[i].second);
        count++;
      }
    }
 
    // Finally return the ans
    return count+1;
  }
 
  public static void main(String[] args)
  {
     
    // Given starting and ending time
    int S[] = {1, 8, 3, 2, 6};
    int E[] = {5, 10, 6, 5, 9};
 
    // Given K and N
    int K = 2, N = S.length;
 
    // Function call
    System.out.println(maximumShops(S, E, N, K));
  }
  static class Pair {
    public int first;
    public int second;
 
    public Pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
  }
 
}
 
// This code is contributed by aadityaburujwale.

Python3

# Python3 program for the above approach
from bisect import bisect_left
 
# Function to find maximum shops
# that can be visited by K persons
def maximumShops(opening, closing, n, k):
 
    # Store opening and closing
    # time of shops
    a = [[0, 0] for i in range(n)]
 
    for i in range(n):
        a[i][0] = opening[i]
        a[i][1] = closing[i]
 
    # Sort the pair of array
    a = sorted(a,key=lambda x: x[1])
     
    # Stores the result
    count = 1
 
    # Stores current number of persons visiting
    # some shop with their ending time
    st = {}
    for i in range(n):
 
        # Check if current shop can be
        # assigned to a person who's
        # already visiting any other shop
        flag = False
 
        if (len(st) == 0):
            ar = list(st.keys())
 
            it = bisect_left(ar, a[i][0])
 
            if (it != 0):
                it -= 1
 
                # Checks if there is any person whose
                # closing time <= current shop opening
                # time
                if (ar[it] <= a[i][0]):
 
                    # Erase previous shop visited by the
                    # person satisfying the condition
                    del st[it]
 
                    # Insert new closing time of current
                    # shop for the person satisfying ?he
                    # condition
                    st[a[i][1]] = 1
 
                    # Increment the count by one
                    count += 1
                    flag = True
 
        # In case if no person have closing
        # time <= current shop opening time
        # but there are some persons left
        if (len(st) < k and flag == False):
            st[a[i][1]] = 1
            count += 1
 
    # Finally print the ans
    return count
 
# Driver Code
if __name__ == '__main__':
 
    # Given starting and ending time
    S = [1, 8, 3, 2, 6]
    E = [5, 10, 6, 5, 9]
 
    # Given K and N
    K,N = 2, len(S)
 
    # Function call
    print (maximumShops(S, E, N, K))
 
    # This code is contributed by mohit kumar 29

C#

using System;
using System.Linq;
using System.Collections.Generic;
 
public class GFG {
    public static int maximumShops(int[] opening, int[] closing, int n, int k) {
 
        // Store opening and closing time of shops
        Pair[] a = new Pair[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Pair(opening[i], closing[i]);
        }
 
        // Sort the pair of array
        Array.Sort(a, new Comparison<Pair>((x, y) => {
            if (x.second != y.second) {
                return x.second - y.second;
            }
            return x.first - y.first;
        }));
 
        // Stores the result
        int count = 0;
 
        // Stores current number of persons visiting
        // some shop with their ending time
        SortedSet<int> st = new SortedSet<int>();
 
        for (int i = 0; i < n; i++) {
 
            // Check if current shop can be assigned to
            // a person who's already visiting any other shop
            bool flag = false;
 
            if (st.Any()) {
                int it = st.Where(x => x > a[i].first).FirstOrDefault();
                if (it <= a[i].first) {
 
                    // Erase previous shop visited by 
                    // the person satisfying the condition
                    st.Remove(it);
 
                    // Insert new closing time of current shop 
                    // for the person satisfying the condition
                    st.Add(a[i].second);
 
                    // Increment the count by one
                    count++;
                    flag = true;
                }
            }
 
            // In case if no person have 
            // closing time <= current shop opening time
            // but there are some persons left
            if (st.Count < k && flag == false) {
                st.Add(a[i].second);
                count++;
            }
        }
 
        // Finally return the ans
        return count;
    }
 
    public static void Main(string[] args) {
 
        // Given starting and ending time
        int[] S = { 1, 8, 3, 2, 6 };
        int[] E = { 5, 10, 6, 5, 9 };
 
        // Given K and N
        int K = 2, N = S.Length;
 
        // Function calla
        Console.WriteLine(maximumShops(S, E, N, K));
    }
 
    public class Pair {
        public int first;
        public int second;
 
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}

Javascript

// Function to find maximum shops
// that can be visited by K persons
function maximumShops(opening, closing, n, k) {
 
  // Store opening and closing
  // time of shops
  const a = new Array(n);
  for (let i = 0; i < n; i++) {
    a[i] = [opening[i], closing[i]];
  }
 
  // Sort the pair of array
  a.sort((x, y) => x[0] - y[0]);
 
  // Stores the result
  let count = 1;
 
  // Stores current number of persons visiting
  // some shop with their ending time
  const st = {};
  for (let i = 0; i < n; i++) {
 
    // Check if current shop can be
    // assigned to a person who's
    // already visiting any other shop
    let flag = false;
 
    if (Object.keys(st).length === 0) {
      const ar = Object.keys(st);
 
      let it = bisect_left(ar, a[i][0]);
 
      if (it !== 0) {
        it -= 1;
 
        // Checks if there is any person whose
        // closing time <= current shop opening
        // time
        if (ar[it] <= a[i][0]) {
 
          // Erase previous shop visited by the
          // person satisfying the condition
          delete st[it];
 
          // Insert new closing time of current
          // shop for the person satisfying ?he
          // condition
          st[a[i][1]] = 1;
 
          // Increment the count by one
          count += 1;
          flag = true;
        }
      }
    }
 
    // In case if no person have closing
    // time <= current shop opening time
    // but there are some persons left
    if (Object.keys(st).length < k && flag === false) {
      st[a[i][1]] = 1;
      count += 1;
    }
  }
 
  // Finally return the result
  return count;
}
 
// Driver Code
(() => {
  // Given starting and ending time
  const S = [1, 8, 3, 2, 6];
  const E = [5, 10, 6, 5, 9];
 
  // Given K and N
  const K = 2, N = S.length;
 
  // Function call
  console.log(maximumShops(S, E, N, K));
})();
 
function bisect_left(arr, x) {  
  let lo = 0;
  let hi = arr.length;
 
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] < x) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
 
  return lo;
}
 
// This code is contributed by sdeadityasharma

Output

Time complexity: O(NlogN)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Activity selection problem with K persons

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US