this algorithm finds the most overlapping activities(bands) in specific intervals that start at arrl and ending at depr.I used quicksort for O(nlogn) time complexity and then a while loop with O(n) to count the number of conflicting activities at these intervals 1.So is this like O(nlogn) + O(n) time complexity? 2.Can i make it even faster at O(n)? 3.Lastly,theoretically,is it possible to use Timsort for O(n) time complexity?
Code written in C is for 15 activities,but let's say it's generalized and with unsorted arrl and depr
EDIT:The result is the most activities at a 1 hour period
void findMaxBands(int n,int arr1[n],int depr[n]);
void quickSort(int a[],int l,int h);
int partition(int a[],int l,int h);
int main(){
int arrl[15] = {18,18,19,19,19,19,20,20,20,20,21,22,22,22,23};
int depr[15] = {19,21,20,21,22,23,21,22,22,23,23,23,24,24,24};
int n = 15;
findMaxBands(n,arrl,depr);
return 0;
}
void findMaxBands(int n,int arrl[n],int depr[n]){
quickSort(arrl,0,15);
quickSort(depr,0,15);
int guestsIn = 1,maxGuests = 1,time = arrl[0];
int i = 1, j = 0;
while (i < n && j < n){
if (arrl[i] <= depr[j]){
guestsIn++;
if (guestsIn > maxGuests){
maxGuests = guestsIn;
time = arrl[i];
}
i++;
}
else{
guestsIn--;
j++;
}
}
printf("Maximum Number of Bands : %d at time %d-%d",maxGuests,time-1,time);
}
void quickSort(int a[],int l,int h){
int j;
if(l<h){
j=partition(a,l,h);
quickSort(a,l,j-1);
quickSort(a,j+1,h);
}
}
int partition(int a[],int l,int h){
int v,i,j,temp;
v=a[l];
i=l;
j=h+1;
do{
do{
i++;
}while(a[i]<v&&i<=h);
do{
j--;
}while(v<a[j]);
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
1.So is this like O(nlogn) + O(n) time complexity?
O(n log(n)) + O(n) = O(n log(n))
Ref. eg. Big O when adding together different routines for more details.
2.Can i make it even faster at O(n)?
3.Lastly,theortically,is it possible to use Timsort for O(n) time complexity?
A general purpose (comparison) sort algorithm might have a best case complexity of O(n), but the average/worst case would have a complexity of O(n log(n)) at best. You can find an overview of several sort algorithms here with their complexities.