Activity Selection Problem

In and Activity Selection Problem we are given a set of activities with their start and finish time, the task is to find out the maximum number of activities completed by a single person, assuming that the person can perform only a single activity at a time.

Input: {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}}
Output: [1,4][5,7][8,11][12,14]

We can solve this problem in O(n logn) time with constant space, the idea is to first sort the set of activities in increasing order of their finishing time, then start iterating the list.

Create a list "nonConf" of activities to contain non-conflicting activities and add first activity from "activities" to it. Now start iterating "activities" from second element, if startTime of the the current element is grater than or equals to the endTime of last added element - add current element to "nonConf". Keep track of index of last added element with a variable "k", initialize k with "0" and update it with "i" every time an element is added to "nonConf".

package com.cd.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ActivitySelectionProblem {

	private static int arr[][] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8},
			{5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};

	private static List<Activity> nonConflicting(List<Activity> activities) {

		// Non conflicting activities
		List<Activity> nonConf = new ArrayList<>();

		// Sort activities in increasing order of ending time
		Collections.sort(activities, (o1, o2) -> o1.getEnd() - o2.getEnd());

		// add first element to it
		nonConf.add(activities.get(0));
		int k = 0;

		// start from second element
		for (int i = 1; i < activities.size(); i++) {
			if (activities.get(i).getStart() >= activities.get(k).getEnd()) {
				nonConf.add(activities.get(i));
				k = i;
			}
		}
		return nonConf;
	}

	public static void main(String[] args) {

		List<Activity> activities = new ArrayList<>();
		for (int i = 0; i < arr.length; i++)
			activities.add(new Activity(arr[i][0], arr[i][1]));

		System.out.println("Activities: ");
		activities.stream().forEach(System.out::print);

		System.out.println();
		System.out.println("Non conflicting Activities: ");
		nonConflicting(activities).stream().forEach(System.out::print);
	}
}

class Activity {
	private int start;
	private int end;
	public Activity(int start, int end) {
		super();
		this.start = start;
		this.end = end;
	}
	public int getStart() {
		return start;
	}
	public void setStart(int start) {
		this.start = start;
	}
	public int getEnd() {
		return end;
	}
	public void setEnd(int end) {
		this.end = end;
	}
	@Override
	public String toString() {
		return "[" + start + "," + end + "]";
	}
}
Output: The output of above shown example will be something like this.

Activities: 
[1,4][3,5][0,6][5,7][3,8][5,9][6,10][8,11][8,12][2,13][12,14]

Non conflicting Activities: 
[1,4][5,7][8,11][12,14]