InterviewBit-Day5

发表于 | 分类于
| 字数统计 525 | 阅读时长 3

Practice

Merge Intervals

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9] insert and merge [2,5] would result in [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] would result in [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Make sure the returned intervals are also sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> res = new ArrayList<>();
        for (Interval interval : intervals) {
            if (interval.end < newInterval.start) {
                res.add(interval);
            } else if (interval.start > newInterval.end) {
                res.add(newInterval);
                newInterval = interval;
            } else if (interval.end >= newInterval.start || 
            interval.start <= newInterval.end) {
                int newStart = Math.min(interval.start, newInterval.start);
                int newEnd = Math.max(interval.end, newInterval.end);
                newInterval = new Interval(newStart, newEnd);
            }
        }
        
        res.add(newInterval);
        return res;
    }
}

Wave Array

Given an array of integers, sort the array into a wave like array and return it,
In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

Example

Given [1, 2, 3, 4]

One possible answer : [2, 1, 4, 3]
Another possible answer : [4, 1, 3, 2]

NOTE : If there are multiple answers possible, return the one thats lexicographically smallest.
So, in example case, you will return [2, 1, 4, 3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public ArrayList<Integer> wave(ArrayList<Integer> A) {
        ArrayList<Integer> res = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        
        temp = quickSort(A, 0, A.size() - 1);
        
        for (int i = 0, j = 1; i < temp.size() - 1 && j < temp.size(); i += 2, j += 2) {
            res.add(temp.get(j));
            res.add(temp.get(i));
        }
        if (temp.size() % 2 != 0) {
            res.add(temp.get(temp.size() - 1));
        }
        // Collections.reverse(res);
        return res;
    }
    
    private ArrayList<Integer> quickSort(ArrayList<Integer> array, int start, int end) {
        if (start < end) {
            int partitionIndex = partition(array, start, end);
            quickSort(array, start, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, end);
        }
        return array;
    }
    
    private int partition(ArrayList<Integer> array, int start, int end) {
        int pivot = array.get(end);
        int partitionIndex = start;
        
        for (int i = start; i < end; i++) {
            if (array.get(i) < pivot) {
                int temp = array.get(i);
                array.set(i, array.get(partitionIndex));
                array.set(partitionIndex, temp);
                partitionIndex++;
            }
        }
        
        int temp = array.get(partitionIndex);
        array.set(partitionIndex, array.get(end));
        array.set(end, temp);
        return partitionIndex;
    }
}
0%