0

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);
}
Certifill
  • 25
  • 5
  • 1
    [codereview.se] might be a better place for a question like this. – Barmar Dec 03 '18 at 09:14
  • If you have discrete intervals of small size (as in your example) then you might also want to look at hashing. Basically for each interval you increase the counter for all points in time with which the interval overlaps. Afterwards you scan through the timestamps and check for the largest counter. The complexity will be O(n * I) where I is the average length of an interval. – SaiBot Dec 03 '18 at 09:41
  • Indeed.All of the intervals must be l=1 hour so it can work.The thing is that i have to write pseudocode afterwards based on the program and it will be complicated – Certifill Dec 03 '18 at 11:28

1 Answers1

1

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.

Community
  • 1
  • 1
Sander De Dycker
  • 16,053
  • 1
  • 35
  • 40
  • thank you very much.Could I implemented it theoretically? – Certifill Dec 03 '18 at 11:13
  • 1
    @Certifill : a comparison based sort algorithm cannot have an average time complexity better than O(n log(n)) (ref. eg. https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf) – Sander De Dycker Dec 03 '18 at 12:06