[HackerRank] Merge and Sort Intervals

Merge and Sort Intervals

Difficulty: Medium

Given an array of intervals [startTime, endTime], merge all overlapping intervals and return a sorted array of non-overlapping intervals.

Example

Input

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

Output

[[1, 6], [8, 10], [15, 18]]

Explanation

- Step 1: Sort intervals by start time (already sorted). 
- Step 2: Initialize merged list with first interval [1,3]. 
- Step 3: Compare [2,6] with last merged [1,3]. They overlap (2 ≤ 3), so merge into [1,6]. Step 4: Compare [8,10] with last merged [1,6]. No overlap (8 > 6), append [8,10]. 
- Step 5: Compare [15,18] with last merged [8,10]. No overlap (15 > 10), append [15,18]. 

Result: [[1,6],[8,10],[15,18]].

Input Format

• The first line contains an integer denoting the number of intervals.
• The second line contains an integer denoting the length of individual interval array.
• Each of the next N lines contains two space-separated integers startTime and endTime
• Intervals may be provided in any order; duplicates and fully contained intervals are allowed.

Example

4
2
1 3
2 6
8 10
15 18

here, 4 is the number of intervals, 2 is the length of individual interval array, followed by the intervals.

Constraints

• 0 <= intervals.length <= 100000
• intervals[i].length == 2 for all 0 <= i < intervals.length
• 0 <= intervals[i][0] < intervals[i][1] <= 10^9 for all 0 <= i < intervals.length

Output Format

• Return a 2D array of two space-separated integers start and end, representing the merged intervals sorted by increasing start time.

Sample Input 0

0
0

Sample Input 1

1
2
5 10

Sample Output 1

5 10

Consideration:

1. Sorting the intervals by each element's startTime.

2. Check if the previous interval overlapped the current interval.

3. Going to the next interval.

Code:

 /*

 * Complete the 'mergeHighDefinitionIntervals' function below.

 *

 * The function is expected to return a 2D_INTEGER_ARRAY.

 * The function accepts 2D_INTEGER_ARRAY intervals as parameter.

 */

vector<vector<int>> mergeHighDefinitionIntervals(vector<vector<int>> intervals) {

    int n = intervals.size();

    vector<vector<int>> outIntervals;

    if (n == 0) return {{}};

    //sort first.

    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {

        return a[0] < b[0]; // Sort by start_time

    });

   

    outIntervals.push_back(intervals[0]);

    for (int i=1;i<n;i++) {

        if (outIntervals.back()[1] >= intervals[i][0]) {

            if (outIntervals.back()[1] < intervals[i][1]) {

                outIntervals.back()[1] = intervals[i][1];

            }

        }

        else {

            outIntervals.push_back(intervals[i]);

        }

    }

    return outIntervals;

}

[HackerRank] Count Elements Greater Than Previous Average

Count Elements Greater Than Previous Average

Difficulty: Easy.

Given an array of positive integers, return the number of elements that are strictly greater than the average of all previous elements. Skip the first element.

Example

Input

responseTimes = [100, 200, 150,300]

Output

2

Explanation

- Day 0: 100 (no previous days, skip) 
- Day 1: 200 > average(100) = 100 → count = 1 
- Day 2: 150 vs average(100, 200) = 150 → not greater → count = 1 
- Day 3: 300 > average(100, 200, 150) = 150 → count = 2 Return 2.

Input Format

• The first line contains an integer n (0 ≤ n ≤ 1000), the number of days.
• If n > 0, the next n lines contains an integer representing responseTimes[i].
• If n = 0, the second line is omitted or empty.

Example

4
100
200
150
300

here 4 is the length of array, followed by the elements of array on each line.

Constraints

• 0 <= responseTimes.length <= 1000
• 1 <= responseTimes[i] <= 10^9 for 0 <= i < responseTimes.length

Output Format

• A single integer depicting the count of days.
  
  

Consideration:

    1. When length of vector is less than 2, the output is always 0.

    2. 10^9 * 1000 > 2^32. So, a normal 32 bits integer couldn't represent big enough summation. Therefore, set "long sum;".

    3. Can't use "responseTimes[i] * i" (Exceeds range of 2^32). Has to divide sum with i and compare with responseTimes[i]. 

Code:

/*

 * Complete the 'countResponseTimeRegressions' function below.

 *

 * The function is expected to return an INTEGER.

 * The function accepts INTEGER_ARRAY responseTimes as parameter.

 */

int countResponseTimeRegressions(vector<int> responseTimes) {

    int n = responseTimes.size();

    //cout << "n = " << n << "\n";

    long sum=0;

    if (n==0) return 0;

    if (n==1) return 0;

    sum = (long) responseTimes[0];

    int i, count=0;

    for (i=1;i<n;i++) {

        if (responseTimes[i]>sum/i) {

            count++;

        }

        sum+=responseTimes[i];

    }

   

    return count;

}

21. Merge Two Sorted Lists

難度: Easy

類型: Linked list,Recursion 

CPP程式下載: 21.cpp

Topic:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Consideration:

Linked List combined.

1. Compare and add the smaller one. Move pointer to next. When one list is ended, add the rest of another list.

2. If both lists empty, return nullptr.

Code:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        //int iSize1=list1.size();

        //int iSize2=list2.size();

        //int i=0,j=0;

        ListNode* outlist=nullptr;

        ListNode* outlistHead=nullptr;

        ListNode* list1tmp=list1;

        ListNode* list2tmp=list2;

        if (list1==nullptr) {

            return list2;

        }

        else if (list2==nullptr) {

            return list1;

        }

        else

        {

            

            while (1) {

                if (list2->val<list1->val) {

                     if (outlistHead==nullptr) {

                         //cout << "list2->val=" << list2->val << "\n";

                         outlist=list2;

                         list2=list2->next;

                         outlistHead=outlist;

                     }

                     else {

                         //cout << "list2->val=" << list2->val << "\n";

                         

                         outlist->next=list2;

                         list2=list2->next;

                         outlist=outlist->next;

                     }

                }

                else {

                    if (outlistHead==nullptr) {

                        outlist=list1;

                         list1=list1->next;

                         outlistHead=outlist;

                    }

                    else {

                         outlist->next=list1;

                         list1=list1->next;

                         outlist=outlist->next;

                     }

                }

                if (list1==nullptr)

                {

                    outlist->next=list2;

                    //cout << "A:list2->val=" << list2->val << "\n";

                    return outlistHead;

                }

                else if (list2==nullptr)

                {

                    outlist->next=list1;

                    return outlistHead;

                }

            }

        }

    }

};

Result:
https://leetcode.com/problems/merge-two-sorted-lists/submissions/1831161763/

Accepted

208 / 208 testcases passed

tendchen

submitted at Nov 16, 2025 16:45

Runtime

0ms

Beats100.00%

Memory

19.58MB

Beats26.66%