gigilibala
BAN USERThe answer can easily be found in linear time.
min_range = (minimum of all range.end)
max_range = if (maximum of all range.begin) > min_range ? (maximum of all range.begin) : (the next number in all ranges after min_range).
The time complexity is depending on input: O(number of ranges) or O(total number of elements in all the ranges)
space complexity O(1), time complexity O(N)
It seems quite easy, I don't understand why it should be done in O(Nlog(N)).
#include <stdio.h>
#include <stdlib.h>
int main(){
int* arr;
int pn, pp;
int nn = 0, np = 0;
int i, N;
scanf("%d", &N);
if(N < 0)
return 0;
arr = (int*)malloc(sizeof(int)*N);
for(i=0; i<N; i++){
scanf("%d", &arr[i]);
}
for(i=0; i<N; i++){
if(arr[i] < 0)
nn++;
}
pn = 0;
pp = nn;
int ppp = pp;
while(1){
while(arr[pn] < 0 && pn < ppp)
pn++;
while(arr[pp] >= 0 && pp < N)
pp++;
if(pn < ppp && pp < N){
int p = arr[pn];
arr[pn] = arr[pp];
arr[pp] = p;
}else
break;
pn++;
pp++;
}
for(i=0; i<N; i++){
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
- gigilibala February 15, 2016