CareerCup

This one a tricky question, it does seem easy at first but when you try with values like [0,6] , [1,2],[3,5] you will notice what goes wrong,

so this is the solution,
0. we should store the old indices of ranges in a map.
1. then we should sort the intervals according to start then according to end
2. we will keep track of the latest merged range and compare it with the new range, its a dynamic programming solution, where we will assume the first merged range is range number zero in the sorted ranges array.

3. we will iterate through the sorted range array from index 1 to end, and check
if( current range intersect with latest merged range ) {
latest marge range = { min( current range.start , mergedRange.start ) ,
max( current range.end , mergedRange.end )
}

if( i -1 == 0) // to consider the first element that we put in the range
add 0 result vector;

add current range *Original* index ( before the sort ) to the result vector
}else{
latest merged range = current range;
}

5. sort the result vector

6. return the result vector;

here is the code, this solution is O(nlogN) , since the sort takes the most of the time.

template<>
class hash< pair<int, int> >
{
public:
	bool operator()(const pair<int, int>& p)const {
		return hash<int>()(p.first) ^ hash<int>()(p.second);
	}
};

bool isInRange(int index, pair<int, int> range) {
	return index >= range.first && index <= range.second;
}

vector<int> findOverlapps(vector<pair<int, int> > & jobs) {

	if (jobs.size() <= 1)
		return{};

	unordered_map<pair<int, int>, int > rangeOrgIndexMap;

	for (int i = 0; i < jobs.size(); i++) {
		rangeOrgIndexMap[jobs[i]] = i;
	}

	vector<int> overlappIndex;

	vector<pair<int, int> > sortedJobs = jobs;

	sort(sortedJobs.begin(), sortedJobs.end());

	pair<int, int> mergedRange = sortedJobs[0];

	for (int i = 1; i < sortedJobs.size() ; i++) {

		if( isInRange(sortedJobs[i].first, mergedRange) || isInRange(sortedJobs[i].second, mergedRange) ) {
			
			mergedRange = { min(sortedJobs[i].first , mergedRange.first) , max(sortedJobs[i].second , mergedRange.second) };

			if (i - 1 == 0)
				overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i-1]]);

			overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i]]);
		}
		else {
			mergedRange = sortedJobs[i];
		}
	}

	sort(overlappIndex.begin(), overlappIndex.end());

	return overlappIndex;
}

My solution is similar to LaithBasilDotNet's, whose code is already very nice under the assumption that the times are hours between 0 and 24: the code is simple and clear and the algorithm is in linear time and constant memory.

I use bit masks instead of the dayTime vector, which allows me to dispense with the inner loops: dup_mask is the bit mask of all hours which appear in at least two job schedules.

#include <vector>
#include <utility>

std::vector<int> find_overlaps(const std::vector<std::pair<int, int>> jobs)
{
    uint32_t seen_mask = 0, dup_mask = 0;
    std::vector<int> result;

    for (const auto &job : jobs) {
        uint32_t mask = (1ul << job.second) - (1ul << job.first);
        dup_mask |= seen_mask & mask;
        seen_mask |= mask;
    }
    for (int i = 0; i != jobs.size(); i++) {
        uint32_t mask = (1ul << jobs[i].second) - (1ul << jobs[i].first);
        if ((mask & dup_mask) != 0)
            result.push_back(i);
    }

    return result;
}

I think we need to take into consideration both the starting time and the larger value of execution time for a given start time.
eg : - let us take all the jobs started at time 1

[1,2][1,5][1,6]
the largest time for which any job starting at 1 executed = 5
at this point we have to consider all the jobs whose starting time lies between 1 to 5
i.e any job that starts at 2, 3, 4 ,5, 6 also overlaps.

Order the indices based on start and end time such that the start times are ordered in buckets and within those buckets, the end times are ordered.

In your example, we order from

[1,2][5,6][1,5][7,8][1,6]

to

[1,2][1,5][1,6][5,6][7,8]

Now iterate through these indices. As long as:

end time of the previous index > start time of current index

this index will be in a set.

A day has hours between 0 and 23.

Keep a integer array (say hours) of 24 elements.For each job schedule increment the hour which is the part of schedule.
For example For job [1,2] increment hours[1] by one and hour[2] by one
Do this for all job schedules
Finally iterate through all hours of day.Hours which has count > 1 has conflicts.

Time complexity : O(noOfJobs);
SpaceComplexity : O(24) = O(1); // only array of 24 is required

We need to create RangeSets for all job schedule times. With two scans of schedule sets, we can create all RangeSets.

input: [1,2] [5,10] [7,8] [11,12] [1,6] [10,11] [20,21] [30,31] [11,20]
1st scan (RangeSets) : [1, 6] [5, 20] [11,12] [20,21] [30,31]
2nd scan (RangeSets) : [1,21] [30,31]

Final step: Now, using RangeSets, we can create the set of overlapping indices
return: [0,1,2,3,4,5,6,8]

Time Complexity: 1st scan = O(n)
2nd scan = O(n)
3rd scan = O(n)

Total = O(n) +O(n) +O(n) = O(n)

Idea is to find all closures of the set. Maintain a queue of remaining jobs (haven't been added to any closure yet). Start by choosing any job from remaining jobs queue and add it to the current closure. Then recurse on every job added to the current closure and do the same thing. Do this until every job is added to some closure (even if it means a closure with just itself).

Best case runtime: O(n) when every job is part of the same closure
Worst case: O(n^2) when every job is in a different closure by itself

public Set<Set<Job>> getClosures(Set<Job> jobs) {

	Set<Set<Job>> closures = new Set<Set<Job>>();
	Set<Job> currentClosure = null;

	while (!jobs.isEmpty()) {

		// Reset current closure
		currentClosure = new Set<Job>();

		// Grab some job that hasn't been added to any closure yet
		Job currJob = getNextJob(jobs);

		// Remove job from remaining jobs and add to current closure
		jobs.remove(currJob);
		currentClosure.add(currJob);

		// Compute closure of current job
		Queue<Job> jobsAddedToClosure = new Queue<Job>();
		jobsAddedToClosure.enqueue(currJob);
		while (!jobsAddedToClosure.isEmpty()) {
			Job job = jobsAddedToClosure.dequeue();
			for (Job j : jobs) {
				// If a job not added to any closure yet intersects with this job,
				// add it to this closure and remove it from the set of jobs not
				// added to any closure
				if (intersects(j, job)) {
					currentClosure.add(j);
					jobsAddedToClosure.enqueue(j);
					jobs.remove(j);
				}
			}
		}

		// Add closure of current job into result set
		closures.add(currentClosure);
	}

	return closures;
}

Sort list of jobs by start and end times (in that order). Iterate through resulting list checking for overlaps. This requires only one iteration since sorting this way guarantees that if job i does not overlap with job i-1, then all jobs i and later do not overlap with any jobs i-1 and earlier.

First, each job needs to implement Comparable, ex:
public int compareTo(Job j) {
	if (this.start < j.start) return -1;
	if (this.start > j.start) return 1;
	if (this.end < j.end) return -1;
	if (this.end > j.end) return 1;
	return 0;
}

public Set<Set<Job>> getOverlappingSets(Job [] jobs) {
	
	Set<Set<Job>> overlappingSets = new Set<Set<Job>>();
	if (jobs == null || jobs.length == 0) {
		return overlappingSets;
	}

	// Sort jobs ascending based on start times, then end times
	Arrays.sort(jobs);

	// Compute overlapping sets
	// Start with adding first job
	Set<Job> currentOverlappingSet = new Set<Job>();
	currentOverlappingSet.add(jobs[0]);
	int prevEnd = jobs[0].end;
	for (int i = 1; i < jobs.length; i++) {
		// If this job overlaps with the previous job's end
		// add it to the current set and update prevEnd
		if (jobs[i].start < prevEnd) {
			currentOverlappingSet.add(jobs[i]);
			prevEnd = jobs[i].end;
		} else {
			// This job does not overlap
			// Add previous set to results if it has overlaps
			if (currentOverlappingSet.length > 1) {
				overlappingSets.add(currentOverlappingSet);
			}
			// Start new set and add this job to it
			currentOverlappingSet = new Set<Job>();
			currentOverlappingSet.add(jobs[i]);
		}
	}

	return overlappingSets;
}

Runtime: O(nlgn) mainly due to sort operation

It's important to understand why we need to sort by start times then end times. This primarily allows us to iterate over the jobs in a single pass.

We couldn't accomplish this if we sorted first by end times.
Ex. [1,5], [7,10], [3,15] does not guarantee that if job i does not overlap with job i-1 that job i+1 will also not overlap. In this case, you'd have to back-track to figure out that [7,10] actually should be included.

This wouldn't work if we just sorted by start times either.
Ex. [1,5], [1,3], [4,5]. The problem is identical to the one above. [4,5] should be included, but we wouldn't know this without back-tracking and looking at [1,5].

1) Put jobs into a map where the key is the hour and the value is the vector of job indices.

2) Loop over the map and place overlaps (where there is more than one index in an hour) into a set.

3) Convert the set to a vector

std::vector<int> getIndexes(std::vector<std::pair<int, int>>& sets)
{
	std::map<int, std::vector<int>> schedule;
	std::set<int> dups;

	int index = 0;

	// construct the schedule
	for (const auto& p : sets)
	{
		for (int i = p.first; i <= p.second; ++i)
		{
			schedule[i].push_back(index);
		}
		++index;
	}

	for (const auto& p : schedule)
	{
		if (p.second.size() > 1)
		{
			for (const auto& d : p.second)
			{
				dups.insert(d);
			}
		}
	}

	return std::vector<int>(dups.begin(), dups.end());
}

Actually it is interesting that people though that the time were hours in a single day which seems to allow linear time algorithms.

I myself though of times out of something so time could be more than a 24 hour boundary.

public static IEnumerable<int> FindIntersections(Tuple<int, int>[] TS)
{
	// int => first, Tuple<int, int> => largest range, int => position
	var sorted = new SortedDictionary<int, Tuple<Tuple<int, int>, int>>();
	
	HashSet<int> result = new HashSet<int>();
	
	for(int i = 0; i < TS.Length; i++)
	{
		var ts = TS[i];
		
		// Probably the best approach is to is a HashTable first to remove
		// intersections so lookups are O(1) rather than O(logn)
		if(sorted.ContainsKey(ts.Item1))
		{
			var val = sorted[ts.Item1];
			result.Add(i);
			result.Add(val.Item2);
			if(val.Item1.Item2 < ts.Item2)
			{
				sorted[ts.Item1] = new Tuple<Tuple<int, int>, int>(ts, i);
			}
		}
		else
		{
			sorted.Add(ts.Item1, new Tuple<Tuple<int, int>, int>(ts, i));
		}
	}
	
	var prev = new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(-1, -1), -1);
	foreach(var kvp in sorted)
	{
		if(prev.Item1.Item2 > kvp.Key)
		{
			result.Add(prev.Item2);
			result.Add(kvp.Value.Item2);
		}
		
		prev = kvp.Value;
	}
	
	result.Remove(-1);
	
	// It is not sorted
	return result;
}

public static Group{
    LinkedList<Integer> setIndices = new LinkedList<Integer>();
    int min;
    int max;

    Group merge(Group g){
        if(g.min < min){
            min = g.min;
        }
        if(g.max > max){
            max = g.max;
        }
        setIndices.addAll(g.setIndices);
    }

    boolean overlaps(Group g){
        return !( max < g.min || min > g.max);
    }

    int[] getSets(){
        int[] results = new int[setIndices.size()];
        Iterator<Integer> iterator = setIndices.iterator();
        for(int i = 0; i < results.length; i++){
            results[i] = iterator.next();
        }
        return results;
    }
}

public static int[][] getOverlaps(int[][] schedules){
    //if feeling froggy, sort the schedules somehow here
    LinkedList<Group> groups = new LinkedList<Group>();
    for(int i = 0; i < schedules.length; i++){
        int[] sched : schedules[i];
        Group g = new Group;
        g.setIndices.add(i);
        g.min = sched[0];
        g.max = sched[1];
    }   
    LinkedList<Group> complete = new LinkedList<Group>();
    boolean merged = true;
    while(groups.size() > 0){
        Group check = groups.removeFirst();
        boolean notMerged = true;
        for(int i = 0; i < groups.size(); i++){
            Group temp = groups.removeFirst();
            if(check.overlaps(temp)){
                check.merge(temp);
                notMerged = false;
            else{
                groups.add(temp);
            }
        }
        if(notMerged){
            if(check.setIndices.size() > 1){
                complete.add(check);
            }
        }
        else{
            groups.add(check);
        }
    }
    int[][] results = new int[complete.()][];
    for(int i = 0; i < complete.size(); i++){
        results[i] = complete.removeFirst().getSets();
    }
    return results;
}

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
overlaps.add(i);
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
overlaps.add(i);
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

public class FindOverlapJobs {

public static List<Integer> findOverLappingJobs(Job[] jobs) {
int[] hours = new int[24];
List<Integer> overlaps = new ArrayList<Integer>();
for (int i = 0; i < jobs.length; i++) {
for (int j = jobs[i].getStartTime(); j <= jobs[i].getEndTime(); j++) {
hours[j] = hours[j] + 1;
}
}

for (int i = 0; i < jobs.length; i++) {
if ((hours[jobs[i].getStartTime()] > 1) || (hours[jobs[i].getEndTime()] > 1)) {
overlaps.add(i);
}
}
return overlaps;

}

public static void main(String[] args) {
Job[] jobs = new Job[5];
jobs[0] = new Job(1, 2);
jobs[1] = new Job(5, 6);
jobs[2] = new Job(1, 5);
jobs[3] = new Job(7, 8);
jobs[4] = new Job(1, 6);
System.out.println(findOverLappingJobs(jobs));
}
}

O(nlogn)

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Interval {
    int index = 0;
    int left;
    int right;
    
    Interval(int left, int right) : left(left), right(right) {}
};

vector<int> getOverllaped(vector<Interval> intervals) {
    vector<int> res;
    if (intervals.empty()) return res;
    
    // store original indices before sorting
    for (int i = 0; i != intervals.size(); ++i)
        intervals[i].index = i;
                         
    // sort by left value
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b){ return a.left < b.left; });
    
    Interval interval = intervals[0];
    for (int i = 1; i != intervals.size(); ++i) {
        if (interval.right < intervals[i].left) {
            interval = intervals[i];
        } else {
            if (i == 1) res.push_back(intervals[0].index);
            res.push_back(intervals[i].index);
            interval = Interval(min(interval.left, intervals[i].left), max(interval.right, intervals[i].right));
        }
    }
    return res;
}

int main()
{
    vector<Interval> intervals;
    intervals.push_back(Interval(1, 2));
    intervals.push_back(Interval(5, 6));
    intervals.push_back(Interval(1, 5));
    intervals.push_back(Interval(7, 8));
    intervals.push_back(Interval(1, 6));
    
    cout <<  "Overllapped: ";
    vector<int> res = getOverllaped(intervals);
    for (int i = 0; i != res.size(); ++i)
        cout << res[i] << " ";
            
}

R

input <- "[1,2][5,6][1,5][7,8][1,6]"
j <- input
j <- gsub(pattern='\\[','',j)
j <- strsplit(j, ']')[[1]]
j <- sapply(j,FUN=strsplit,split=',')
pairs <- matrix(as.numeric(unlist(j)),byrow=T, ncol=2)


myRange <- function(data){
  return(seq(from=data[1], data[2], by=1))
}

ls <- apply(pairs, 1,FUN= myRange)

getOverlappingSets <- function(ls){
  inside <- c()
  for(i in 1:(length(ls))){
    count <- 0
    for(j in 1:length(ls)){
      if( i != j ){
        if(any(ls[[i]] %in% ls[[j]])){
          count <- count + 1
        }
      }
    }
    if(count > 0){
      inside <- c(inside, i)
    }
  }
  return(inside)
}

getOverlappingSets(ls)

# test case
x = floor(runif(8,0,9)*10)
y = x + floor(runif(8, 1, 10))*3
pairs <- data.frame(x,y)
ls <- apply(pairs, 1,FUN= myRange)
getOverlappingSets(ls)

package com.home.project.test;

import java.util.HashMap;

/*Given set of job schedules with start and end time, write a function that returns indexes of overlapping sets.

 for ex :- 
 input -> [1,2][5,6][1,5][7,8][1,6]
 return -> [0,1,2,4]*/

public class OverlapSet {

	HashMap<Integer, String> inputMap;
	int inputmapSize = 0;
	int[][] inputAList;


	public OverlapSet() {
		inputMap = new HashMap();
		inputAList = new int[100][2];

	}

	private void populate(int startNum, int endNum) {

		if (startNum < endNum) {
			inputAList[inputmapSize][0] = startNum;
			inputAList[inputmapSize][1] = endNum;
		} else {
			inputAList[inputmapSize][0] = startNum;
			inputAList[inputmapSize][1] = endNum;
		}
		inputmapSize++;
	}

	private void printOverLapSet() {
		for (int i = 0; i < inputmapSize; i++) {
			for (int j = 0; j < inputmapSize; j++) {
				if (i == j)
					continue;
				if (inputAList[j][0] <= inputAList[i][0]
						|| inputAList[j][0] <= inputAList[i][1]
						|| inputAList[j][1] <= inputAList[i][0]
						|| inputAList[j][1] <= inputAList[i][1]) {
					inputMap.put(j, "Overlap");
				}
			}
		}
		for (Integer key : inputMap.keySet()) {

			System.out
					.println("------------------------------------------------");
			System.out.println("key: " + key + " value: " + inputMap.get(key));
		}
	}

	public static void main(String[] args) {
		OverlapSet olSet = new OverlapSet();
		olSet.populate(1, 2);
		olSet.populate(5, 6);
		olSet.populate(1, 5);
		olSet.populate(7, 8);
		olSet.populate(1, 6);
		olSet.printOverLapSet();
	}

}

I got a O(nlogn) and O(n) solution in computation and space respectively.
Here is how the example works out.

Let's take a look at the example: [1, 2], [5, 6], [1, 5], [7, 8], [1, 6]
The sorted lower and upper bounds are,
    - Lower bounds: {1, 1, 1, 5, 7}
    - Upper bounds: {2, 5, 6, 6, 8}
Here is the algorithm runs
    - Take 1 as the lower bound of the first interval
    - Ui = 2, Li+1 = 1, where  i = 1. it is a OVERLAP case and continue
    - Ui = 5, Li+1 = 1, where i = 2, it is a OVERLAP case and continue
    - Ui = 6, Li+1 = 5, where i = 3, it is a OVERLAP case and continue
    - Ui = 6, Li+1 = 7, where i = 4, it is NOT a OVERLAP case
        * The first interval stops her as [1, 6]
        * The second interval starts here with lower bound as 7
    - Reach the end, construct the second interval with the upper bound of Un, [7, 8]
Two overlapped intervals generated as [1, 6] and [7, 8]
Insert key 1 with empty vector and key 7 with empty vector into hash map,
Order the overlapped interval's lower bounds as {1, 7}
    - Task [1, 2]: the 1st value <= 1 is 1. then append 0 into the value of Key 1 of hash map
    - Task [5, 6]: the 1st value <= 5 is 1. then append 1 into the value of Key 1 of hash map
    - Task [1, 5]: the 1st value <= 1 is 1. then append 2 into the value of Key 1 of hash map
    - Task [7, 8]: the 1st value <= 7 is 7. then append 3 into the value of Key 7 of hash map
    - Task [1, 6]: the 1st value <= 1 is 1. then append 4 into the value of Key 1 of hash map
Go through the hash map,
    [0, 1, 2, 4] in one group
    [3] in one group

More details about the algorithm and pseudo-code, please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/06/data-structure-and-algorithm-find.html